On degree sum conditions for long cycles and cycles through specified vertices

Let G be a graph. For S⊂V(G), let Δ_k(S) denote the maximum value of the degree sums of the subsets of S of order k. In this paper, we prove the following two results. (1) Let G be a 2-connected graph. If Δ₂(S)≥d for every independent set S of order κ(G)+1, then G has a cycle of length at least min{d,|V(G)|}. (2) Let G be a 2-connected graph and X a subset of V(G). If Δ₂(S)≥|V(G)| for every independent set S of order κ(X)+1 in G[X], then G has a cycle that includes every vertex of X. This suggests that the degree sum of nonadjacent two vertices is important for guaranteeing the existence of these cycles.     

Properties of connected graphs having minimum degree distance

The degree distance of a connected graph, introduced by Dobrynin, Kochetova and Gutman, has been studied in mathematical chemistry. In this paper some properties of graphs having minimum degree distance in the class of connected graphs of order n and size m≥n−1 are deduced. It is shown that any such graph G has no induced subgraph isomorphic to P₄, contains a vertex z of degree n−1 such that G−z has at most one connected component C such that |C|≥2 and C has properties similar to those of G.For any fixed k such that k=0,1 or k≥3, if m=n+k and n≥k+3 then the extremal graph is unique and it is isomorphic to K₁+(K_1,k+1∪(n−k−3)K₁).     

Degree conditions for the partition of a graph into cycles, edges and isolated vertices

Let k,n be integers with 2≤k≤n, and let G be a graph of order n. We prove that if max{d_G(x),d_G(y)}≥(n−k+1)/2 for any x,y∈V(G) with x≠y and xy∉E(G), then G has k vertex-disjoint subgraphs H₁,…,H_k such that V(H₁)∪?∪V(H_k)=V(G) and H_i is a cycle or K₁ or K₂ for each 1≤i≤k, unless k=2 and G=C₅, or k=3 and G=K₁∪C₅.     

Degree Conditions and Degree Bounded Trees

In this paper, we give sufficient conditions for a graph to have degree bounded trees. Let G be a connected graph and $A\subseteq V(G)$. We denote by ${\sigma }_k(A)$ the minimum value of the degree sum in G of any k pairwise nonadjacent vertices of A, and by $w(G-A)$ the number of components of the subgraph $G-A$ of G induced by $V(G)-A$. Our main results are the following: (i) If ${\sigma }_k(A)⩾|G|-1$, then G contains a tree T with maximum degree ⩽k and $A\subseteq V(T)$. (ii) If ${\sigma }_{k-w(G-A)}(A)⩾|A|-1$, then G contains a spanning tree T with $d_T(x)⩽k$ for any $x\in A$. These are generalizations of the result by S. Win [S. Win, Existenz von Gerüsten mit Vorgeschriebenem Maximalgrad in Graphen, Abh. Math. Seminar Univ. Humburg 43 (1975) 263–267] and degree conditions are sharp.     

A generalization of Fan’s results: Distribution of cycle lengths in graphs

Fan [G. Fan, Distribution of cycle lengths in graphs, J. Combin. Theory Ser. B 84 (2002) 187-202] proved that if G is a graph with minimum degree δ(G)≥3k for any positive integer k, then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if δ(G)≥3k+1, then |E(C_k)|−|E(C_k−1)|=2. In this paper, we generalize Fan’s result, and show that if we let G be a graph with minimum degree δ(G)≥3, for any positive integer k (if k≥2, then δ(G)≥4), if d_G(u)+d_G(v)≥6k−1 for every pair of adjacent vertices u,v∈V(G), then G contains k+1 cycles C₀,C₁,…,C_k such that k+1<|E(C₀)|<|E(C₁)|<?<|E(C_k)|, |E(C_i)−E(C_i−1)|=2, 1≤i≤k−1, and 1≤|E(C_k)|−|E(C_k−1)|≤2, and furthermore, if d_G(u)+d_G(v)≥6k+1, then |E(C_k)|−|E(C_k−1)|=2.     

A note on cycle spectra of line graphs

We show that line graphs G=L(H) with σ₂(G)≥7 contain cycles of all lengths k, 2rad(H)+1≤k≤c(G). This implies that every line graph of such a graph with 2rad(H)≥Δ(H) is subpancyclic, improving a recent result of Xiong and Li. The bound on σ₂(G) is best possible.     

Ordering connected graphs having small degree distances

The concept of degree distance of a connected graph G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D^′(G)=∑_x∈V(G)d(x)∑_y∈V(G)d(x,y), where d(x) and d(x,y) are the degree of x and the distance between x and y, respectively. In this paper it is proved that connected graphs of order n≥4 having the smallest degree distances are K_1,n−1,BS(n−3,1) and K_1,n−1+e (in this order), where BS(n−3,1) denotes the bistar consisting of vertex disjoint stars K_1,n−3 and K_1,1 with central vertices joined by an edge.     

A degree sum condition for graphs to be prism hamiltonian

Win, in 1975, and Jackson and Wormald, in 1990, found the best sufficient conditions on the degree sum of a graph to guarantee the properties of “having a k-tree” and “having a k-walk”, respectively. The property of “being prism hamiltonian” is an intermediate property between “having a 2-tree” and “having a 2-walk”. Thus, it is natural to ask what is the best degree sum condition for graphs to be prism hamiltonian. As an answer to this problem, in this paper, we show that a connected graph G of order n with σ₃(G)≥n is prism hamiltonian. The degree sum condition “σ₃(G)≥n” is best possible.     

Hamiltonian cycles and dominating cycles passing through a linear forest

Let G be an (m+2)-graph on n vertices, and F be a linear forest in G with |E(F)|=m and ω₁(F)=s, where ω₁(F) is the number of components of order one in F. We denote by σ₃(G) the minimum value of the degree sum of three vertices which are pairwise non-adjacent. In this paper, we give several σ₃ conditions for a dominating cycle or a hamiltonian cycle passing through a linear forest. We first prove that if σ₃(G)≥n+2m+2+max{s−3,0}, then every longest cycle passing through F is dominating. Using this result, we prove that if σ₃(G)≥n+κ(G)+2m−1 then G contains a hamiltonian cycle passing through F. As a corollary, we obtain a result that if G is a 3-connected graph and σ₃(G)≥n+κ(G)+2, then G is hamiltonian-connected.     

Removable matchings and hamiltonian cycles

For a graph G, let σ₂(G) denote the minimum degree sum of two nonadjacent vertices (when G is complete, we let σ₂(G)=∞). In this paper, we show the following two results: (i) Let G be a graph of order n≥4k+3 with σ₂(G)≥n and let F be a matching of size k in G such that G−F is 2-connected. Then G−F is hamiltonian or G≅K₂+(K₂∪K_n−4) or ; (ii) Let G be a graph of order n≥16k+1 with σ₂(G)≥n and let F be a set of k edges of G such that G−F is hamiltonian. Then G−F is either pancyclic or bipartite. Examples show that first result is the best possible.     

A constructive characterization of total domination vertex critical graphs

Let G be a graph of order n and maximum degree Δ(G) and let γ_t(G) denote the minimum cardinality of a total dominating set of a graph G. A graph G with no isolated vertex is the total domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, the total domination number of G−v is less than the total domination number of G. We call these graphs γ_t-critical. For any γ_t-critical graph G, it can be shown that n≤Δ(G)(γ_t(G)−1)+1. In this paper, we prove that: Let G be a connected γ_t-critical graph of order n (n≥3), then n=Δ(G)(γ_t(G)−1)+1 if and only if G is regular and, for each v∈V(G), there is an A⊆V(G)−{v} such that N(v)∩A=0?, the subgraph induced by A is 1-regular, and every vertex in V(G)−A−{v} has exactly one neighbor in A.     

Trees through specified vertices

We prove a conjecture of Horak that can be thought of as an extension of classical results including Dirac’s theorem on the existence of Hamiltonian cycles. Namely, we prove for 1≤k≤n−2 if G is a connected graph with A⊂V(G) such that d_G(v)≥k for all v∈A, then there exists a subtree T of G such that V(T)⊃A and for all v∈A.     

Small alliances in a weighted graph

We extend the notion of a defensive alliance to weighted graphs. Let (G,w) be a weighted graph, where G is a graph and w be a function from V(G) to the set of positive real numbers. A non-empty set of vertices S in G is said to be a weighted defensive alliance if ∑_{x∈NG(v)∩S}w(x)+w(v)≥∑_{x∈NG(v)−S}w(x) holds for every vertex v in S. Fricke et al. (2003) [3] have proved that every graph of order n has a defensive alliance of order at most . In this note, we generalize this result to weighted defensive alliances. Let G be a graph of order n. Then we prove that for any weight function w on V(G), (G,w) has a defensive weighted alliance of order at most . We also extend the notion of strong defensive alliance to weighted graphs and generalize a result in Fricke et al. (2003) [3].     

On the Structure of Graphs with Bounded Asteroidal Number

 A set A⊆V of the vertices of a graph G=(V,E) is an asteroidal set if for each vertex a∈A, the set A\{a} is contained in one component of G−N[a]. The maximum cardinality of an asteroidal set of G, denoted by an (G), is said to be the asteroidal number of G. We investigate structural properties of graphs of bounded asteroidal number. For every k≥1, an (G)≤k if and only if an (H)≤k for every minimal triangulation H of G. A dominating target is a set D of vertices such that D∪S is a dominating set of G for every set S such that G[D∪S] is connected. We show that every graph G has a dominating target with at most an (G) vertices. Finally, a connected graph G has a spanning tree T such that d _T (x,y)−d _G (x,y)≤3·|D|−1 for every pair x,y of vertices and every dominating target D of G. Received: July 3, 1998 Final version received: August 10, 1999     

Blockers and transversals in some subclasses of bipartite graphs: When caterpillars are dancing on a grid

Given an undirected graph G=(V,E) with matching number ν(G), a d-blocker is a subset of edges B such that ν((V,E?B))≤ν(G)−d and a d-transversal T is a subset of edges such that every maximum matching M has |M∩T|≥d. While the associated decision problem is NP-complete in bipartite graphs we show how to construct efficiently minimum d-transversals and minimum d-blockers in the special cases where G is a grid graph or a tree.     

Equitable colorings of Kronecker products of graphs

For a positive integer k, a graph G is equitably k-colorable if there is a mapping f:V(G)→{1,2,…,k} such that f(x)≠f(y) whenever xy∈E(G) and ||f⁻¹(i)|−|f⁻¹(j)||≤1 for 1≤i<j≤k. The equitable chromatic number of a graph G, denoted by χ₌(G), is the minimum k such that G is equitably k-colorable. The equitable chromatic threshold of a graph G, denoted by , is the minimum t such that G is equitably k-colorable for k≥t. The current paper studies equitable chromatic numbers of Kronecker products of graphs. In particular, we give exact values or upper bounds on χ₌(G×H) and when G and H are complete graphs, bipartite graphs, paths or cycles.     

The independence number condition for the existence of a spanning f‐tree

Let G be a graph and f be a mapping from V(G) to the positive integers. A subgraph T of G is called an f‐tree if T forms a tree and d_T(x)≤f(x) for any x∈V(T). We propose a conjecture on the existence of a spanning f‐tree, and give a partial solution to it. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 173–184, 2010     

Degree sum and connectivity conditions for dominating cycles

For a graph G, let σ_k(G) be the minimum degree sum of an independent set of k vertices. Ore showed that if G is a graph of order n?3 with σ₂(G)?n then G is hamiltonian. Let κ(G) be the connectivity of a graph G. Bauer, Broersma, Li and Veldman proved that if G is a 2-connected graph on n vertices with σ₃(G)?n+κ(G), then G is hamiltonian. On the other hand, Bondy showed that if G is a 2-connected graph on n vertices with σ₃(G)?n+2, then each longest cycle of G is a dominating cycle. In this paper, we prove that if G is a 3-connected graph on n vertices with σ₄(G)?n+κ(G)+3, then G contains a longest cycle which is a dominating cycle.     

Critically indecomposable graphs

An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a₁,b₁),(a₂,b₂),…,(a_m,b_m) such that G(V−{a_j1,b_j1,…,a_jk,b_jk}) is also an X-critical graph for arbitrary set of indices {j₁,…,j_k}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x₁,y₁),…,(x_t,y_t) such that x_i,y_i∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G.     

Non-separating trees in connected graphs

Let T be any tree of order d≥1. We prove that every connected graph G with minimum degree d contains a subtree T^′ isomorphic to T such that G−V(T^′) is connected.