Search

In 1966 Gallai asked the following question: Do all longest paths (cycles) of a connected graph contain a common vertex? After a positive answer to Gallai's question, another question has been raised, Is there any family of graphs without Gallai's property? Menke found one such family, the square lattices. Embedding methods hold the promise to transform not just the way calculations are performed, but to significantly reduce computational costs and often used in quantum mechanics and material sciences. In this paper, we prove the existence of graphs with the empty intersection of their longest cycles as subgraphs of Archimedean lattices. [ABSTRACT FROM AUTHOR]

An edge e of a graph G is called singular if it is not on a triangle; otherwise, e is nonsingular. A vertex is called singular if it is adjacent to a singular edge; otherwise, it is called nonsingular. We prove the following. Let G be a connected claw-free graph such that every locally disconnected vertex x ∈ V(G) satisfies the following conditions: (i) if x is nonsingular of degree 4, then x is on an induced cycle of length at least 4 with at most 4 nonsingular edges, (ii) if x is not nonsingular of degree 4, then x is on an induced cycle of length at least 4 with at most 3 nonsingular edges, (iii) if x is of degree 2, then x is singular and x is on an induced cycle C of length at least 4 with at most 2 nonsingular edges such that G [ V (C) ∩ V 2 (G) ] is a path or a cycle. Then G is either hamiltonian, or G is the line graph of the graph obtained from K 2 , 3 by attaching a pendant edge to its each vertex of degree two. Some results on forbidden subgraph conditions for hamiltonicity in 3-connected claw-free graphs are also obtained as immediate corollaries [ABSTRACT FROM AUTHOR]

A graph is said to be total-colored if all the edges and the vertices of the graph are colored. A path P in a total-colored graph G is called a total-proper path if (1) any two adjacent edges of P are assigned distinct colors; (2) any two adjacent internal vertices of P are assigned distinct colors; and (3) any internal vertex of P is assigned a distinct color from its incident edges of P. The total-colored graph G is total-proper connected if any two distinct vertices of G are connected by a total-proper path. The total-proper connection number of a connected graph G, denoted by tpc(G), is the minimum number of colors that are required to make G total-proper connected. In this paper, we first characterize the graphs G on n vertices with tpc(G)=n-1. Based on this, we obtain a Nordhaus-Gaddum-type result for total-proper connection number. We prove that if G and G¯ are connected complementary graphs on n vertices, then 6≤tpc(G)+tpc(G¯)≤n+2. Examples are given to show that the lower bound is sharp for n≥4. The upper bound is reached for n≥4 if and only if G or G¯ is the tree with maximum degree n-2. [ABSTRACT FROM AUTHOR]

A path P in an edge-colored graph G is called a proper path if no two adjacent edges of P are colored the same, and G is proper connected if every two vertices of G are connected by a proper path in G. The proper connection number of a connected graph G, denoted by pc(G), is the minimum number of colors that are needed to make G proper connected. In this paper, we investigate the proper connection number of the complement of a graph G according to some constraints of G itself. Also, we characterize the graphs on n vertices that have proper connection number n-2. Using this result, we give a Nordhaus-Gaddum-type theorem for the proper connection number. We prove that if G and G¯ are both connected, then 4≤pc(G)+pc(G¯)≤n, and the upper bound holds if and only if G or G¯ is the n-vertex tree with maximum degree n-2. [ABSTRACT FROM AUTHOR]

In this paper, we explore minimal k-connected non-Hamiltonian graphs. Graphs are said to be minimal in the context of some containment relation; we focus on subgraphs, induced subgraphs, minors, and induced minors. When k=2, we discuss all minimal 2-connected non-Hamiltonian graphs for each of these four relations. When k=3, we conjecture a set of minimal non-Hamiltonian graphs for the minor relation and we prove one case of this conjecture. In particular, we prove all 3-connected planar triangulations which do not contain the Herschel graph as a minor are Hamiltonian. [ABSTRACT FROM AUTHOR]

The Clar number of a (hydro)carbon molecule, introduced by Clar (The aromatic sextet, 1972), is the maximum number of mutually disjoint resonant hexagons in the molecule. Calculating the Clar number can be formulated as an optimization problem on 2-connected plane graphs. Namely, it is the maximum number of mutually disjoint even faces a perfect matching can simultaneously alternate on. It was proved by Abeledo and Atkinson (Linear Algebra Appl 420(2):441-448, 2007) that the Clar number can be computed in polynomial time if the plane graph has even faces only. We prove that calculating the Clar number in general 2-connected plane graphs is $$\mathsf {NP}$$ -hard. We also prove $$\mathsf {NP}$$ -hardness of the maximum independent set problem for 2-connected plane graphs with odd faces only, which may be of independent interest. Finally, we give an exact algorithm that determines the Clar number of a given 2-connected plane graph. The algorithm has a polynomial running time if the length of the shortest odd join in the planar dual graph is fixed, which gives an efficient algorithm for some fullerene classes, such as carbon nanotubes. [ABSTRACT FROM AUTHOR]

The atom-bond connectivity (ABC) index of a graph G is defined to be $$ABC(G)=\sum _{uv\in E(G)}\sqrt{\frac{d(u)+d(v)-2}{d(u)d(v)}}$$ where d( u) is the degree of a vertex u. The ABC index plays a key role in correlating the physical-chemical properties and the molecular structures of some families of compounds. In this paper, we describe the structural properties of graphs which have the minimum ABC index among all connected graphs with a given degree sequence. Moreover, these results are used to characterize the extremal graphs which have the minimum ABC index among all unicyclic and bicyclic graphs with a given degree sequence. [ABSTRACT FROM AUTHOR]

Finding low-cost spanning subgraphs with given degree and connectivity requirements is a fundamental problem in the area of network design. We consider the problem of finding d-regular spanning subgraphs (or d-factors) of minimum weight with connectivity requirements. For the case of k-edge-connectedness, we present approximation algorithms that achieve constant approximation ratios for all d≥2.⌈k/2⌉. For the case of k-vertex-connectedness, we achieve constant approximation ratios for d≥2k-1. Our algorithms also work for arbitrary degree sequences if the minimum degree is at least 2.⌈k/2⌉ (for k-edge-connectivity) or 2k-1 (for k-vertex-connectivity). To complement our approximation algorithms, we prove that the problem with simple connectivity cannot be approximated better than the traveling salesman problem. In particular, the problem is A P X-hard. [ABSTRACT FROM AUTHOR]

The (n, k)-star graphs are an important class of interconnection networks that generalize star graphs, which are superior to hypercubes. In this paper, we continue the work begun by Cheng et al. (Graphs Combin 33(1):85–102, 2017) and complete the classification of all the (n, k)-star graphs that are Cayley. [ABSTRACT FROM AUTHOR]

Let G=H[G1,G2,…,Gk] be the generalized join graph ofG1,G2,…,Gk determined by H. In this paper, we give a decomposition formula for the Bartholdi zeta function of G. As applications, we obtain explicit formulae for Bartholdi zeta functions of some special kinds of graphs, such as the complete multipartite graph, the wheel, etc. [ABSTRACT FROM AUTHOR]

A dominating set in a graph G is a set S of vertices of G such that every vertex not in S has a neighbor in S. Further, if every vertex of G has a neighbor in S, then S is a total dominating set of G. The domination number, γ(G), and total domination number, γt(G), are the minimum cardinalities of a dominating set and total dominating set, respectively, in G. The upper domination number, Γ(G), and the upper total domination number, Γt(G), are the maximum cardinalities of a minimal dominating set and total dominating set, respectively, in G. It is known that γt(G)/γ(G)≤2 and Γt(G)/Γ(G)≤2 for all graphs G with no isolated vertex. In this paper we characterize the connected cubic graphs G satisfying γt(G)/γ(G)=2, and we characterize the connected cubic graphs G satisfying Γt(G)/Γ(G)=2. [ABSTRACT FROM AUTHOR]

A t-tone k-coloring of a graph G=(V,E) is a function f:V→[k]t such that |f(u)∩f(v)| for all distinct vertices u and v. The t-tone chromatic number of G, denoted τt(G), is the smallest positive integer k such that G has a t-tone k-coloring. The Wiener index W(G) of a connected graph G is the sum of the distances of all pairs of vertices of G. In this paper, we prove that τt(G)≥t|V|-W(G)+|V|2 for a connected graph G and obtain a characterization when the equality holds. As a result, for each graph G (not necessarily connected), we obtain a formula for the t-tone chromatic number of G when t is sufficiently large. [ABSTRACT FROM AUTHOR]

We consider the contact process on finite and connected graphs and study the behavior of the extinction time, that is, the amount of time that it takes for the infection to disappear in the process started from full occupancy. We prove, without any restriction on the graph G, that if the infection rate $$\lambda $$ is larger than the critical rate of the one-dimensional process, then the extinction time grows faster than $$\exp \{|G|/(\log |G|)^\kappa \}$$ for any constant $$\kappa > 1$$ , where | G| denotes the number of vertices of G. Also for general graphs, we show that the extinction time divided by its expectation converges in distribution, as the number of vertices tends to infinity, to the exponential distribution with parameter 1. These results complement earlier work of Mountford, Mourrat, Valesin and Yao, in which only graphs of bounded degrees were considered, and the extinction time was shown to grow exponentially in n; here we also provide a simpler proof of this fact. [ABSTRACT FROM AUTHOR]

Consider a setting where possibly sensitive information sent over a path in a network is visible to every neighbor of the path, i.e., every neighbor of some node on the path, thus including the nodes on the path itself. The exposure of a path P can be measured as the number of nodes adjacent to it, denoted by N[ P]. A path is said to be secluded if its exposure is small. A similar measure can be applied to other connected subgraphs, such as Steiner trees connecting a given set of terminals. Such subgraphs may be relevant due to considerations of privacy, security or revenue maximization. This paper considers problems related to minimum exposure connectivity structures such as paths and Steiner trees. It is shown that on unweighted undirected n-node graphs, the problem of finding the minimum exposure path connecting a given pair of vertices is strongly inapproximable, i.e., hard to approximate within a factor of $$O(2^{\log ^{1-\epsilon }n})$$ for any $$\epsilon >0$$ (under an appropriate complexity assumption), but is approximable with ratio $$\sqrt{\Delta }+3$$ , where $$\Delta $$ is the maximum degree in the graph. One of our main results concerns the class of bounded-degree graphs, which is shown to exhibit the following interesting dichotomy. On the one hand, the minimum exposure path problem is NP-hard on node-weighted or directed bounded-degree graphs (even when the maximum degree is 4). On the other hand, we present a polynomial algorithm (based on a nontrivial dynamic program) for the problem on unweighted undirected bounded-degree graphs. Likewise, the problem is shown to be polynomial also for the class of (weighted or unweighted) bounded-treewidth graphs. Turning to the more general problem of finding a minimum exposure Steiner tree connecting a given set of k terminals, the picture becomes more involved. In undirected unweighted graphs with unbounded degree, we present an approximation algorithm with ratio $$\min \{\Delta , n/k, \sqrt{2n},O(\log k \cdot (k+\sqrt{\Delta }))\}$$ . On unweighted undirected bounded-degree graphs, the problem is still polynomial when the number of terminals is fixed, but if the number of terminals is arbitrary, then the problem becomes NP-hard again. [ABSTRACT FROM AUTHOR]

We show an algorithm for dynamic maintenance of connectivity information in an undirected planar graph subject to edge deletions. Our algorithm may answer connectivity queries of the form 'Are vertices u and v connected with a path?" in constant time. The queries can be intermixed with any sequence of edge deletions, and the algorithm handles all updates in a total of O( n) time. This results improves over a previously known O( n log n) time algorithm. [ABSTRACT FROM AUTHOR]

Let D be a digraph on $\{v_{1},\ldots, v_{n}\}$ . Then the sequence $\{ (d^{+}(v_{1}), d^{-}(v_{1})), \ldots, (d^{+}(v_{n}), d^{-}(v_{n}))\}$ is called the degree sequence of D. For any given sequence of pairs of integers $\mathbf{d}=\{(d_{1}^{+}, d_{1}^{-}), \ldots, (d_{n}^{+}, d_{n}^{-})\}$ , if there exists a k-arc strongly connected digraph D such that d is the degree sequence of D, then d is realizable and D is a realization of d. In this paper, characterizations for k-arc-connected realizable sequences and realizable sequences with arc-connectivity exactly k are given. [ABSTRACT FROM AUTHOR]

An edge-coloring of a connected graph is a monochromatically-connecting coloring (MC-coloring, for short) if there is a monochromatic path joining any two vertices, which was introduced by Caro and Yuster. Let mc( G) denote the maximum number of colors used in an MC-coloring of a graph G. Note that an MC-coloring does not exist if G is not connected, in which case we simply let $$mc(G)=0$$ . In this paper, we characterize all connected graphs of size m with $$mc(G)=1, 2, 3, 4$$ , $$m-1$$ , $$m-2$$ and $$m-3$$ , respectively. We use G( n, p) to denote the Erdős-Rényi random graph model, in which each of the $$\left( {\begin{array}{c}n\\ 2\end{array}}\right) $$ pairs of vertices appears as an edge with probability p independent from other pairs. For any function f( n) satisfying $$1\le f(n)<\frac{1}{2}n(n-1)$$ , we show that if $$\ell n \log n\le f(n)<\frac{1}{2}n(n-1)$$ , where $$\ell \in \mathbb {R}^+$$ , then $$p=\frac{f(n)+n\log \log n}{n^2}$$ is a sharp threshold function for the property $$mc\left( G\left( n,p\right) \right) \ge f(n)$$ ; if $$f(n)=o(n\log n)$$ , then $$p=\frac{\log n}{n}$$ is a sharp threshold function for the property $$mc\left( G\left( n,p\right) \right) \ge f(n)$$ . [ABSTRACT FROM AUTHOR]

Let G( V, E) be a connected and undirected graph with n-vertex-set V and m-edge-set E. For each v ∈ V, let N( v) = { u| v ∈ V and( u, v) ∈ E}. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V( G) to a k-bit Boolean string f( v) = f ( v) f ( v) ... f ( v), i.e., f ( v) ∈ {0, 1}, 1 ≤ i ≤ k, such that for any vertex v with f( v) = 0 we have ⋈ f( u) = 1, for all v ∈ V, where ⋈ f( u) denotes the result of taking bitwise OR operation on f( u), for all u ∈ S. The weight of f is defined as $w(f) = {\sum }_{v\in V}{\sum }^{k}_{i=1} f_{i}(v)$ . The k-rainbow domination number γ ( G) is the minimum weight of a k-rainbow dominating function over all k-rainbow dominating functions of G. The 1-rainbow domination is the same as the ordinary domination. The k-rainbow domination problem is to determine the k-rainbow domination number of a graph G. In this paper, we determine γ ( S( n, m)), γ ( S ( n, m)), and γ ( S ( n, m)), where S( n, m), S ( n, m), and S ( n, m) are Sierpiński graphs and extended Sierpiński graphs. [ABSTRACT FROM AUTHOR]

Connections between nodes in optical networks are realized by lightpaths. Due to the decay of the signal, a regenerator has to be placed on every lightpath after at most d hops, for some given positive integer d. A regenerator can serve only one lightpath. The placement of regenerators has become an active area of research during recent years, and various optimization problems have been studied. The first such problem is the Regeneration Location Problem (Rlp), where the goal is to place the regenerators so as to minimize the total number of nodes containing them. We consider two extreme cases of online Rlp regarding the value of d and the number k of regenerators that can be used in any single node. (1) d is arbitrary and k unbounded. In this case a feasible solution always exists. We show an O(log| X|⋅ log d)-competitive randomized algorithm for any network topology, where X is the set of paths of length d. The algorithm can be made deterministic in some cases. We show a deterministic lower bound of ${\Omega } \left (\frac {\log (|{E}|/d) \cdot \log d}{\log (\log (|{E}|/d) \cdot \log d)}\right )$ , where E is the edge set. (2) d = 2 and k = 1. In this case there is not necessarily a solution for a given input. We distinguish between feasible inputs (for which there is a solution) and infeasible ones. In the latter case, the objective is to satisfy the maximum number of lightpaths. For a path topology we show a lower bound of $\sqrt {l}/2$ for the competitive ratio (where l is the number of internal nodes of the longest lightpath) on infeasible inputs, and a tight bound of 3 for the competitive ratio on feasible inputs. [ABSTRACT FROM AUTHOR]

We consider the Geometric Connected Facility Location Problem (GCFLP): given a set of clients $\mathcal {C} \subset \mathbb {R}^{d}$ , one wants to select a set of locations $F \subset \mathbb {R}^{d}$ where to open facilities, each at a fixed cost f≥0. For each client $j \in \mathcal {C}$ , one has to choose to either connect it to an open facility ϕ( j)∈ F paying the Euclidean distance between j and ϕ( j), or pay a given penalty cost π( j). The facilities must also be connected by a tree T, whose cost is M ℓ( T), where M≥1 and ℓ( T) is the total Euclidean length of edges in T. The multiplication by M reflects the fact that interconnecting two facilities is typically more expensive than connecting a client to a facility. The objective is to find a solution with minimum cost. In this paper, we present a Polynomial-Time Approximation Scheme (PTAS) for the two-dimensional GCFLP. Our algorithm also leads to a PTAS for the two-dimensional Geometric Connected k-medians, when f=0, but only k facilities may be opened. [ABSTRACT FROM AUTHOR]

We study the design of small cost temporally connected graphs, under various constraints. We mainly consider undirected graphs of n vertices, where each edge has an associated set of discrete availability instances (labels). A journey from vertex u to vertex v is a path from u to v where successive path edges have strictly increasing labels. A graph is temporally connected iff there is a ( u, v)-journey for any pair of vertices u, v, u ≠ v. We first give a simple polynomial-time algorithm to check whether a given temporal graph is temporally connected. We then consider the case in which a designer of temporal graphs can freely choose availability instances for all edges and aims for temporal connectivity with very small cost; the cost is the total number of availability instances used. We achieve this via a simple polynomial-time procedure which derives designs of cost linear in n. We also show that the above procedure is (almost) optimal when the underlying graph is a tree, by proving a lower bound on the cost for any tree. However, there are pragmatic cases where one is not free to design a temporally connected graph anew, but is instead given a temporal graph design with the claim that it is temporally connected, and wishes to make it more cost-efficient by removing labels without destroying temporal connectivity (redundant labels). Our main technical result is that computing the maximum number of redundant labels is APX-hard, i.e., there is no PTAS unless P = N P. On the positive side, we show that in dense graphs with random edge availabilities, there is asymptotically almost surely a very large number of redundant labels. A temporal design may, however, be minimal, i.e., no redundant labels exist. We show the existence of minimal temporal designs with at least nlog n labels. [ABSTRACT FROM AUTHOR]

The $$W_v$$ -path conjecture due to Klee and Wolfe states that any two vertices of a simple polytope can be joined by a path that does not revisit any facet. This is equivalent to the well-known Hirsch conjecture. Klee proved that the $$W_v$$ -path conjecture is true for all 3-polytopes (3-connected plane graphs), and conjectured even more, namely that the $$W_v$$ -path conjecture is true for all general cell complexes. This general $$W_v$$ -path conjecture was verified for polyhedral maps on the projective plane and the torus by Barnette, and on the Klein bottle by Pulapaka and Vince. Let G be a graph polyhedrally embedded in a surface $$\Sigma $$ , and x, y be two vertices of G. In this paper, we show that if there are three internally disjoint ( x, y)-paths which are homotopic to each other, then there exists a $$W_v$$ -path joining x and y. For every surface $$\Sigma $$ , define a function $$f(\Sigma )$$ such that if for every graph polyhedrally embedded in $$\Sigma $$ and for a pair of vertices x and y in V( G), the local connectivity $$\kappa _G(x,y) \ge f(\Sigma )$$ , then there exists a $$W_v$$ -path joining x and y. We show that $$f(\Sigma )=3$$ if $$\Sigma $$ is the sphere, and for all other surfaces $$3-\tau (\Sigma )\le f(\Sigma )\le 9-4\chi (\Sigma )$$ , where $$\chi (\Sigma )$$ is the Euler characteristic of $$\Sigma $$ , and $$\tau (\Sigma )=\chi (\Sigma )$$ if $$\chi (\Sigma )< -1$$ and 0 otherwise. Further, if x and y are not cofacial, we prove that G has at least $$\kappa _G(x,y)+4\chi (\Sigma )-8$$ internally disjoint $$W_v$$ -paths joining x and y. This bound is sharp for the sphere. Our results indicate that the $$W_v$$ -path problem is related to both the local connectivity $$\kappa _G(x,y)$$ , and the number of different homotopy classes of internally disjoint ( x, y)-paths as well as the number of internally disjoint ( x, y)-paths in each homotopy class. [ABSTRACT FROM AUTHOR]

In this paper, we determine the unique graph whose least signless Laplacian eigenvalue attains the minimum among all non-bipartite unicyclic graphs of order n with maximum degree Δ and among all non-bipartite connected graphs of order n with maximum degree Δ, respectively. [ABSTRACT FROM AUTHOR]

The sets with continuous selection from near-best approximations and the monotone path-connected sets are studied; several examples of such sets are also considered. [ABSTRACT FROM AUTHOR]

Evolution of Earth surface systems (ESS) comprises sequential transitions between system states. Treating these as directed graphs, algebraic graph theory was used to quantify complexity of archetypal structures, and empirical examples of forest succession and alluvial river channel change. Spectral radius measures structural complexity and is highest for fully connected, lowest for linear sequential and cyclic graphs, and intermediate for divergent and convergent patterns. The irregularity index $$\beta $$ represents the extent to which a subgraph is representative of the full graph. Fully connected graphs have $$\beta = 1$$ . Lower values are found in linear and cycle patterns, while higher values, such as those of divergent and convergent patterns, are due to a few highly connected nodes. Algebraic connectivity ( $$\mu (\mathrm{G}))$$ indicates inferential synchronization and is inversely related to historical contingency. Highest values are associated with fully connected and strongly connected mesh graphs, whereas forking structures and linear sequences all have $$\mu (G)$$ = 1, with cycles slightly higher. Diverging vs. converging graphs of the same size and topology have no differences with respect to graph complexity, so complexity change is dependent on whether development results in increased or reduced richness. Convergent-divergent mode switching, however, would generally increase ESS complexity, decrease irregularity, and increase algebraic connectivity. As ESS and associated graphs evolve, none of the possible trends reduces complexity, which can only remain constant or increase. Algebraic connectivity may increase, however. As improving shortcomings in ESS evolution models generally result in elaborating possible state changes, this produces more structurally complex but less historically contingent models. [ABSTRACT FROM AUTHOR]

Let $$G$$ be a $$k$$ -connected graph with $$k\ge 2$$ . In this paper we first prove that: For two distinct vertices $$x$$ and $$z$$ in $$G$$ , it contains a path connecting $$x$$ and $$z$$ which passes through its any $$k-2$$ specified vertices with length at least the average degree of the vertices other than $$x$$ and $$z$$ . Further, with this result, we prove that: If $$G$$ has $$n$$ vertices and $$m$$ edges, then it contains a cycle of length at least $$2m/(n-1)$$ passing through its any $$k-1$$ specified vertices. Our results generalize a theorem of Fan on the existence of long paths and a classical theorem of Erdős and Gallai on the existence of long cycles under the average degree condition. [ABSTRACT FROM AUTHOR]

In this paper, we characterize connected $$\{K_{1,3},N(2,1,0)\}$$ -free but not $$N(1,1,1)$$ -free graphs. By combining our result and a theorem showed by Duffus et al. (every $$2$$ -connected $$\{K_{1,3},N(1,1,1)\}$$ -free graph is Hamiltonian), we give an alternative proof of Bedrossian's theorem (every $$2$$ -connected $$\{K_{1,3},N(2,1,0)\}$$ -free graph is Hamiltonian). [ABSTRACT FROM AUTHOR]

For an integer $$k$$ with $$k \ge 2$$ , a $$k$$ - tree (resp. a $$k$$ - forest) is a tree (resp. forest) with maximum degree at most $$k$$ . In this paper, we show that for any integer $$k$$ with $$k \ge 3$$ , any connected $$K_{1,k+1}$$ -free graph has a spanning $$k$$ -tree or a spanning $$k$$ -forest with only large components. [ABSTRACT FROM AUTHOR]

A vertex-cut $$S$$ of a connected graph $$G$$ is called a restricted vertex-cut if no vertex $$u$$ of the graph $$G$$ satisfies $$N_G(u)\subseteq S$$ . The restricted connectivity $$\kappa '(G)$$ of the graph $$G$$ is the cardinality of a minimum restricted vertex-cut of $$G$$ ; this is a more refined index than the connectivity parameter $$\kappa (G)$$ . In this paper, we prove that $$\kappa '(K_m\times G_2)=2k_2+m-2$$ , where $$G_2$$ is a $$k_2\ (\ge 2)$$ -regular and maximally connected graph with girth $$g(G_2)\ge 4$$ ; and $$\kappa '(G_1\times G_2)=2k_1+2k_2-2$$ , where $$G_i$$ is a $$k_i\ (\ge 2)$$ -regular and maximally connected graph with girth $$g(G_i)\ge 4$$ for $$1\le i\le 2$$ . Furthermore, we determine the restricted connectivity of a class of minimal Abelian Cayley graphs. [ABSTRACT FROM AUTHOR]

By generalizing the path method, we show that nonlinear spectral gaps of a finite connected graph are uniformly bounded from below by a positive constant which is independent of the target metric space. We apply our result to an $$r$$ -ball $$T_{d,r}$$ in the $$d$$ -regular tree, and observe that the asymptotic behavior of nonlinear spectral gaps of $$T_{d,r}$$ as $$r\rightarrow \infty $$ does not depend on the target metric space, which is in contrast to the case of a sequence of expanders. We also apply our result to the $$n$$ -dimensional Hamming cube $$H_n$$ and obtain an estimate of its nonlinear spectral gap with respect to an arbitrary metric space, which is asymptotically sharp as $$n\rightarrow \infty $$ . [ABSTRACT FROM AUTHOR]

If a graph has a unique perfect matching, we call it a UPM-graph. In this paper we study UPM-graphs. It was shown by Kotzig that a connected UPM-graph has a cut edge belonging to its unique perfect matching. We strengthen this result to a further structural characterization. Using the stronger result, we present a characterization of claw-free UPM-graphs, and prove that for any fixed positive integer $$n$$ , the number of edges of saturated UPM-graphs on $$2n$$ vertices form an arithmetic progression from $$(2n+2)\lfloor \log _2(n+1)\rfloor -2^{2+\lfloor \log _2(n+1)\rfloor }+n+4$$ to $$n^2$$ with common difference 2. For a fixed positive integer $$n$$ , we determine the number of labelled UPM-trees on $$2n$$ vertices. For a bipartite UPM-graph which has maximum number of edges, we determine the number of spanning UPM-trees of it. [ABSTRACT FROM AUTHOR]

A parity subgraph of a graph is a spanning subgraph such that the degrees of all vertices have the same parity in both the subgraph and the original graph. Let $$G$$ be a cyclically 6-edge-connected cubic graph. Steffen (Intersecting 1-factors and nowhere-zero 5-flows , ) proved that $$G$$ has a nowhere-zero 5-flow if $$G$$ has two perfect matchings with at most two intersections. In this paper, we show that $$G$$ has a nowhere-zero 5-flow if $$G$$ has two parity subgraphs with at most two common edges, which generalizes Steffen's result. [ABSTRACT FROM AUTHOR]

A facial parity edge-coloring of a $$2$$ -edge-connected plane graph is such an edge-coloring in which no two face-adjacent edges receive the same color and in addition, for each face $$f$$ and each color $$c$$ either no edge or an odd number of edges incident with $$f$$ is colored with $$c$$ . Let $$\chi _p^\prime (G)$$ denote the minimum number of colors used in such a coloring of $$G$$ . In this paper we prove that $$\chi _p^\prime (G)\le 9$$ for any $$2$$ -edge-connected outerplane graph $$G$$ with one exception. Moreover, we show that this bound is tight. [ABSTRACT FROM AUTHOR]

Chvátal and Erdős proved a well-known result that every graph $$G$$ with connectivity $$\kappa (G)$$ not less than its independence number $$\alpha (G)$$ is Hamiltonian. Han et al. (in Discret Math 310:2082-2090, ) showed that every 2-connected graph $$G$$ with $$\alpha (G)\le \kappa (G)+1$$ is supereulerian with some exceptional graphs. In this paper, we investigate the similar conditions and show that every 2-connected graph $$G$$ with $$\alpha (G)\le \kappa (G)+3$$ has a spanning trail. We also show that every connected graph $$G$$ with $$\alpha (G)\le \kappa (G)+2$$ has a spanning trail or $$G$$ is the graph obtained from $$K_{1,3}$$ by replacing at most two vertices of degree 1 in $$K_ {1,3}$$ with a complete graph or $$G$$ is the graph obtained from $$K_{3}$$ by adding a pendent edge to each vertex of $$K_{3}$$ . As a byproduct, we obtain that the line graph of a connected graph $$G$$ with $$\alpha (G)\le \kappa (G)+2$$ is traceable. These results are all best possible. [ABSTRACT FROM AUTHOR]

Given a finite nonempty set of primes S, we build a graph $${\mathcal{G}}$$ with vertex set $${\mathbb{Q}}$$ by connecting $${x, y \in \mathbb{Q}}$$ if the prime divisors of both the numerator and denominator of x − y are from S. In this paper we resolve two conjectures posed by Ruzsa concerning the possible sizes of induced nondegenerate cycles of $${\mathcal{G}}$$ , and also a problem of Ruzsa concerning the existence of subgraphs of $${\mathcal{G}}$$ which are not induced subgraphs. [ABSTRACT FROM AUTHOR]

An edge-colored graph G is rainbow connected if every pair of vertices of G are connected by a path whose edges have distinct colors. The rainbow connection number rc( G) of G is defined to be the minimum integer t such that there exists an edge-coloring of G with t colors that makes G rainbow connected. For a graph G without any cut vertex, i.e., a 2-connected graph, of order n, it was proved that $${rc(G)\leq\lceil\frac{n}{2} \rceil}$$ and the bound is tight. In this paper, we prove that for a connected graph G of order n with at least one cut vertex, $${rc(G) \leq\frac{n+r-1} 2}$$ , where r is the number of blocks of G with even orders, and the upper bound is tight. Moreover, we also obtain a tight upper bound $${\lfloor(2n-2)/3\rfloor}$$ for the rainbow connection number of a bridgeless (2-edge-connected) graph of order n. [ABSTRACT FROM AUTHOR]

For a simple graph G, the graph's spread s( G) is defined as the difference between the largest eigenvalue and the least eigenvalue of the graph's adjacency matrix, i.e. $${s(G)=\rho(G)-\lambda(G)}$$ . A connected graph G is a cactus if any two of its cycles have at most one common vertex. If all cycles of the cactus G have exactly one common vertex then it is called a bundle. Let $${{\mathcal C}(n,k)}$$ denote the class of cacti with n vertices and k cycles. In this paper, we determine a unique cactus whose spread is maximal among the cacti with n vertices and k cycles. We prove that the obtained graph is a bundle of a special form. Within the class $${{\mathcal C}(n,k)}$$ we also present a unique cactus whose least eigenvalue is minimal (Petrović et al. in Linear Algebra Appl 435:2357-2364, ) and show that these two graphs are the same, except for a few cases in which n is small. [ABSTRACT FROM AUTHOR]

A hexangulation G is a 2-connected simple plane graph such that each face of G is bounded by a 6-cycle. It was recently proved that any two hexangulations with the same number of vertices can be transformed into each other by three specifically defined transformations $${\mathbb{A}, \mathbb{B}}$$ and $${\mathbb{C}}$$ . We prove that any two hexangulations G and G′ with bipartitions { B, W} and { B′, W′}, respectively, such that | B| = | B′| and | W| = | W′|, can be transformed into each other by successive applications of operations in $${\{\mathbb{A}, \mathbb{B}^2, \mathbb{C}\}}$$ . Moreover, we completely describe the role of the four operations $${\mathbb{A}, \mathbb{B}, \mathbb{B}^2}$$ and $${\mathbb{C}}$$ in the transition diagram of hexangulations. [ABSTRACT FROM AUTHOR]

In this paper, the cycle structures for directed graphs on surfaces are studied. If G is a strongly connected graph, C is a Π- contractible directed cycle of G, then both of Int( C,Π) and Ext( C,Π) are strongly connected graph; the dimension of cycles space of G is identified. If G is a strongly connected graph, then the structure of MCB in G is unique. Let G be a strongly connected graph, if G has been embedded in orientable surface S with f( G) ≥ 2 ( f( G) is the face-width of G), then any cycle base of G must contain at least 2 g noncontractible directed cycles; if G has been embedded in non-orientable surface N, then any cycle base of G must contain at least g noncontractible directed cycles. [ABSTRACT FROM AUTHOR]

Is it proves that every connected graph with s vertices of degree 1 and 3 anf t vertices of degree at least 4 has a spanning tree with at least $ \frac{1}{3}t + \frac{1}{4}s + \frac{3}{2} $ leaves. Infinite series of grpahs showing that our bound is tight are given. [ABSTRACT FROM AUTHOR]

Let D be a strongly connected digraph on n ≥ 4 vertices. A vertex v of D is noncritical if the digraph D − v is strongly connected. It is proved that if the sum of degrees of any two adjacent vertices of D is at least n + 1, then there exists a noncritical vertex in D, and if the sum of degrees of any two adjacent vertices of D is at least n + 2, then there exist two noncritical vertices in D. A series of examples confirms that these bounds are tight. Bibliography: 4 titles. [ABSTRACT FROM AUTHOR]

It is proved that every connected graph with s vertices of degree 3 and t vertices of degree at least 4 has a spanning tree with $ \frac{2}{5}t+\frac{1}{5}s+\alpha $ leaves, where $ \alpha \geq \frac{8}{5} $. Moreover, α ≥ 2 for all graphs, except for three exclusions. All exclusions are regular graphs of degree 4, and they are explicitly described in the paper. An infinite series of graphs containing only vertices of degree 3 and 4, for which the maximal number of leaves in a spanning tree is equal to $ \frac{2}{5}t+\frac{1}{5}s+2 $, is presented. Therefore it is proved that the bound is tight. Bibliography: 12 titles. [ABSTRACT FROM AUTHOR]

The algebraic connectivity of a graph is the second smallest eigenvalue of the associated Laplacian matrix. In this paper, we not only characterize the extremal graphs with the maximal algebraic connectivity among all graphs of order n with given matching number, but also determine the extremal tree with the maximal algebraic connectivity among all trees of order n with given matching number. [ABSTRACT FROM AUTHOR]

For integers i, j, k with $${i\geq j\geq k\geq 0}$$, let N be the graph obtained by identifying end vertices of three disjoint paths of lengths i, j, k to the vertices of a triangle. In this paper, we show that every 3-connected { K, N}-free graph is hamiltonian, where $${i \in \{4,5\}}$$ . This result is sharp in the sense that no one of the numbers i, 7− i and 2 in N can be replaced by a larger number. [ABSTRACT FROM AUTHOR]

Let G be a 2-edge-connected simple graph on n ≥ 14 vertices, and let A be an abelian group with the identity element 0. If a graph G* is obtained by repeatedly contracting nontrivial A-connected subgraphs of G until no such a subgraph left, we say that G can be A-reduced to G*. In this paper, we prove that if for every $${uv\not\in E(G), |N(u) \cup N(v)| \geq \lceil \frac{2n}{3} \rceil}$$, then G is not Z-connected if and only if G can be Z-reduced to one of $${\{C_3,K_4,K_4^-, L\}}$$, where L is obtained from K by adding a new vertex which is joined to two vertices of K. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. The notion of rainbow connection number rc( G) of a graph G was introduced by Chartrand et al. (Math Bohem 133:85-98, ). Basavaraju et al. (arXiv:1011.0620v1 [math.CO], ) proved that for every bridgeless graph G with radius r, $${rc(G)\leq r(r+2)}$$ and the bound is tight. In this paper, we show that for a connected graph G with radius r and center vertex u, if we let D = { u}, then G has r−1 connected dominating sets $${ D^{r-1}, D^{r-2},\ldots, D^{1}}$$ such that $${D^{r} \subset D^{r-1} \subset D^{r-2} \cdots\subset D^{1} \subset D^{0}=V(G)}$$ and $${rc(G)\leq \sum_{i=1}^{r} \max \{2i+1,b_i\}}$$, where b is the number of bridges in E[ D, N( D)] for $${1\leq i \leq r}$$. From the result, we can get that if $${b_i\leq 2i+1}$$ for all $${1\leq i\leq r}$$, then $${rc(G)\leq \sum_{i=1}^{r}(2i+1)= r(r+2)}$$; if b > 2 i + 1 for all $${1\leq i\leq r}$$ , then $${rc(G)= \sum_{i=1}^{r}b_i}$$, the number of bridges of G. This generalizes the result of Basavaraju et al. In addition, an example is given to show that there exist infinitely graphs with bridges whose rc( G) is only dependent on the radius of G, and another example is given to show that there exist infinitely graphs with bridges whose rc( G) is only dependent on the number of bridges in G. [ABSTRACT FROM AUTHOR]

Spanning connectivity of graphs has been intensively investigated in the study of interconnection networks (Hsu and Lin, Graph Theory and Interconnection Networks, ). For a graph G and an integer s > 0 and for $${u, v \in V(G)}$$ with u ≠ v, an ( s; u, v)-path-system of G is a subgraph H consisting of s internally disjoint ( u, v)-paths. A graph G is spanning s-connected if for any $${u, v \in V(G)}$$ with u ≠ v, G has a spanning ( s; u, v)-path-system. The spanning connectivity κ*( G) of a graph G is the largest integer s such that G has a spanning ( k; u, v)-path-system, for any integer k with 1 ≤ k ≤ s, and for any $${u, v \in V(G)}$$ with u ≠ v. An edge counter-part of κ*( G), defined as the supereulerian width of a graph G, has been investigated in Chen et al. (Supereulerian graphs with width s and s-collapsible graphs, ). In Catlin and Lai (Graph Theory, Combinatorics, and Applications, vol. 1, pp. 207-222, ) proved that if a graph G has 2 edge-disjoint spanning trees, and if L( G) is the line graph of G, then κ*( L( G)) ≥ 2 if and only if κ( L( G)) ≥ 3. In this paper, we extend this result and prove that for any integer k ≥ 2, if G, the core of G, has k edge-disjoint spanning trees, then κ*( L( G)) ≥ k if and only if κ( L( G)) ≥ max{3, k}. [ABSTRACT FROM AUTHOR]

We show that there is a well-defined family of connected simple graphs Λ( n, m) on n vertices and m edges such that all graphs in Λ( n, m) have the same number of spanning trees, and if $${G \in \Lambda(n, m)}$$ then the number of spanning trees in G is strictly less than the number of spanning trees in any other connected simple graph $${H, H \notin \Lambda(n, m)}$$ , on n vertices and m edges. [ABSTRACT FROM AUTHOR]

An edge cut of a connected graph is 5-restricted if its removal leaves every component having order at least five. Graphs that contain 5-restricted edge cuts are characterized in this paper. As a result, it is shown that a connected graph G of order at least 13 contains 5-restricted edge cuts if and only if $${G \setminus v}$$ contains a component of order at least five for every vertex v of graph G. [ABSTRACT FROM AUTHOR]

The concept of group connectivity was introduced by Jaeger et al. (J Comb Theory Ser B 56:165-182, ) for the study of integer flows. The concept of all generalized Tutte-orientations was introduced by Barát and Thomassen (J Graph Theory 52:135-146, ) for the study of claw-decompositions of graphs. In this paper, we establish the equivalence of the following 3 properties: a graph is $$\mathcal{Z}_3$$-connected, a graph admits all generalized Tutte-orientations and a graph is 3-flow contractible. We also give some applications of this result. [ABSTRACT FROM AUTHOR]