Interpolation theorem for the number of end-vertices of spanning trees

The following interpolation theorem is proved: If a graph G contains spanning trees having exactly m and n end-vertices, with m < n, then for every integer k, m < k < n, G contains a spanning tree having exactly k end-vertices. This settles a problem posed by Chartrand at the Fourth International Conference on Graph Theory and Applications held in Kalamazoo, 1980.     

A lower bound on the number of spanning trees with k end-vertices

If a graph G with cycle rank ρ contains both spanning trees with m and with n end-vertices, m < n, then G has at least 2ρ spanning trees with k end-vertices for each integer k, m < k < n. Moreover, the lower bound of 2ρ is best possible.     

Subgraphs with Restricted Degrees of Their Vertices in Planar 3-Connected Graphs

We have proved that every 3-connected planar graph G either contains a path on k vertices each of which has degree at most 5k or does not contain any path on k vertices; the bound 5k is the best possible. Moreover, for every connected planar graph H other than a path and for every integer m ≥ 3 there is a 3-connected planar graph G such that each copy of H in G contains a vertex of degree at least m.     

Edge-deletable IM-extendable graphs with minimum number of edges

A graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. For a nonnegative integer k, a graph G is called a k-edge-deletable IM-extendable graph, if, for every F⊆E(G) with |F|=k, G−F is IM-extendable. In this paper, we characterize the k-edge-deletable IM-extendable graphs with minimum number of edges. We show that, for a positive integer k, if G is ak-edge-deletable IM-extendable graph on 2n vertices, then |E(G)|≥(k+2)n; furthermore, the equality holds if and only if either G≅K_k+2,k+2, or k=4r−2 for some integer r≥3 and G≅C₅[N_2r], where N_2r is the empty graph on 2r vertices and C₅[N_2r] is the graph obtained from C₅ by replacing each vertex with a graph isomorphic to N_2r.     

(3,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7. Revised: September 21, 1998     

Spanning Star Trees in Regular Graphs

For a subset W of vertices of an undirected graph G, let S(W) be the subgraph consisting of W, all edges incident to at least one vertex in W, and all vertices adjacent to at least one vertex in W. If S(W) is a tree containing all the vertices of G, then we call it a spanning star tree of G. In this case W forms a weakly connected but strongly acyclic dominating set for G. We prove that for every r ≥ 3, there exist r-regular n-vertex graphs that have spanning star trees, and there exist r-regular n-vertex graphs that do not have spanning star trees, for all n sufficiently large (in terms of r). Furthermore, the problem of determining whether a given regular graph has a spanning star tree is NP-complete.     

Steiner Numbers in Graphs

Abstract

The Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence s_o(G),s₁ (G),…,8_p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized.     

Conditional colorings of graphs

For an integer r>0, a conditional(k,r)-coloring of a graph G is a proper k-coloring of the vertices of G such that every vertex of degree at least r in G will be adjacent to vertices with at least r different colors. The smallest integer k for which a graph G has a conditional (k,r)-coloring is the rth order conditional chromatic number χ_r(G). In this paper, the behavior and bounds of conditional chromatic number of a graph G are investigated.     

Four gravity results

The gravity of a graph H in a given family of graphs H is the greatest integer n with the property that for every integer m, there exists a supergraph G∈H of H such that each subgraph of G, which is isomorphic to H, contains at least n vertices of degree ?m in G. Madaras and Škrekovski introduced this concept and showed that the gravity of the path P_k on k?2 vertices in the family of planar graphs of minimum degree 2 is k-2 for each k≠5,7,8,9. They conjectured that for each of the four excluded cases the gravity is k-3. In this paper we show that this holds.     

Path-Star Ramsey numbers

Let f(m,n) be the least integer N such that for every graph G with N vertices, either G contains a path of m vertices or the complement of G contains a vertex of degree at least n. This paper determines f(m,n) for all m, n.     

{k,r – k}-Factors of r-Regular Graphs

For a set \({\mathcal{S}}\) of positive integers, a spanning subgraph F of a graph G is called an \({\mathcal{S}}\) -factor of G if \({\deg_F(x) \in \mathcal{S}}\) for all vertices x of G, where deg _F (x) denotes the degree of x in F. We prove the following theorem on {a, b}-factors of regular graphs. Let r ≥ 5 be an odd integer and k be either an even integer such that 2 ≤ k < r/2 or an odd integer such that r/3 ≤ k < r/2. Then every r-regular graph G has a {k, r–k}-factor. Moreover, for every edge e of G, G has a {k, r–k}-factor containing e and another {k, r–k}-factor avoiding e.     

On n-Hamiltonian line graphs

With each nonempty graph G one can associate a graph L(G), called the line graph of G, with the property that there exists a one-to-one correspondence between E(G) and V(L(G)) such that two vertices of L(G) are adjacent if and only if the corresponding edges of G are adjacent. For integers m ≥ 2, the mth iterated line graph L^m(G) of G is defined to be L(L^m-1(G)). A graph G of order p ≥ 3 is n-Hamiltonian, 0 ≤ n ≤ p ? 3, if the removal of any k vertices, 0 ≤ k ≤ n, results in a Hamiltonian graph. It is shown that if G is a connected graph with δ(G) ≥ 3, where δ(G) denotes the minimum degree of G, then L²(G) is (δ(G) ? 3)-Hamiltonian. Furthermore, if G is 2-connected and δ(G) ≥ 4, then L²(G) is (2δ(G) ? 4)-Hamiltonian. For a connected graph G which is neither a path, a cycle, nor the graph K(1, 3) and for any positive integer n, the existence of an integer k such that L^m(G) is n-Hamiltonian for every m ≥ k is exhibited. Then, for the special case n = 1, bounds on (and, in some cases, the exact value of) the smallest such integer k are determined for various classes of graphs.     

Spanning 3-ended trees in k-connected K 1,4-free graphs

A tree with at most m leaves is called an m-ended tree.Kyaw proved that every connected K1,4-free graph withσ4(G)n-1 contains a spanning 3-ended tree.In this paper we obtain a result for k-connected K1,4-free graphs with k 2.Let G be a k-connected K1,4-free graph of order n with k 2.Ifσk+3(G)n+2k-2,then G contains a spanning 3-ended tree.     

High Connectivity Keeping Sets In <Emphasis Type="Italic">n</Emphasis>-Connected Graphs

It is proved that for every positive integer k, every n-connected graph G of sufficiently large order contains a set W of k vertices such that G—W is (n-2)-connected. It is shown that this does not remain true if we add the condition that G(W) is connected.     

The factorial representation of balanced labelled graphs

Consider a graph G with m edges and m+1 vertices. Label the vertices of G from 0 to m. Label each edge with the positive difference of its end labels. If these edge labels take on the values from 1 to m, the graph is said to be properly labelled. If, in addition, the end labels x,y of each edge satisfy x ? r < y for some fixed integer r, the proper labelling is balanced. We introduce sequences of integers to represent properly labelled graphs. Using these sequences, we count balanced labelled graphs as well as a subclass of these which possess symmetry.     

The equivariant topology of stable Kneser graphs

The stable Kneser graph SG_n,k, n?1, k?0, introduced by Schrijver (1978) [19], is a vertex critical graph with chromatic number k+2, its vertices are certain subsets of a set of cardinality m=2n+k. Björner and de Longueville (2003) [5] have shown that its box complex is homotopy equivalent to a sphere, Hom(K₂,SG_n,k)?Sk. The dihedral group D2m acts canonically on SG_n,k, the group C₂ with 2 elements acts on K₂. We almost determine the (C₂×D2m)-homotopy type of Hom(K₂,SG_n,k) and use this to prove the following results.The graphs SG_2s,4 are homotopy test graphs, i.e. for every graph H and r?0 such that Hom(SG_2s,4,H) is (r−1)-connected, the chromatic number χ(H) is at least r+6.If k∉{0,1,2,4,8} and n?N(k) then SG_n,k is not a homotopy test graph, i.e. there are a graph G and an r?1 such that Hom(SG_n,k,G) is (r−1)-connected and χ(G)<r+k+2.     

Pancyclic graphs and linear forests

Given integers k,s,t with 0≤s≤t and k≥0, a (k,t,s)-linear forest F is a graph that is the vertex disjoint union of t paths with a total of k edges and with s of the paths being single vertices. If the number of single vertex paths is not critical, the forest F will simply be called a (k,t)-linear forest. A graph G of order n≥k+t is (k,t)-hamiltonian if for any (k,t)-linear forest F there is a hamiltonian cycle containing F. More generally, given integers m and n with k+t≤m≤n, a graph G of order n is (k,t,s,m)-pancyclic if for any (k,t,s)-linear forest F and for each integer r with m≤r≤n, there is a cycle of length r containing the linear forest F. Minimum degree conditions and minimum sum of degree conditions of nonadjacent vertices that imply that a graph is (k,t,s,m)-pancyclic (or just (k,t,m)-pancyclic) are proved.     

Spanning Trees with a Bounded Number of Branch Vertices in a Claw-Free Graph

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed.     

Connected graphs with maximal Q-index: The one-dominating-vertex case

By the signless Laplacian of a (simple) graph G we mean the matrix Q(G)=D(G)+A(G), where A(G),D(G) denote respectively the adjacency matrix and the diagonal matrix of vertex degrees of G. For every pair of positive integers n,k, it is proved that if 3?k?n-3, then H_n,k, the graph obtained from the star K_1,n-1 by joining a vertex of degree 1 to k+1 other vertices of degree 1, is the unique connected graph that maximizes the largest signless Laplacian eigenvalue over all connected graphs with n vertices and n+k edges.     

Rainbow Connection Number and Radius

The rainbow connection number, rc(G), of a connected graph G is the minimum number of colours needed to colour its edges, so that every pair of its vertices is connected by at least one path in which no two edges are coloured the same. In this note we show that for every bridgeless graph G with radius r, rc(G) ≤  r(r + 2). We demonstrate that this bound is the best possible for rc(G) as a function of r, not just for bridgeless graphs, but also for graphs of any stronger connectivity. It may be noted that for a general 1-connected graph G, rc(G) can be arbitrarily larger than its radius (K _1,n for instance). We further show that for every bridgeless graph G with radius r and chordality (size of a largest induced cycle) k, rc(G) ≤  rk. Hitherto, the only reported upper bound on the rainbow connection number of bridgeless graphs is 4n/5 ? 1, where n is order of the graph (Caro et al. in Electron J Comb 15(1):Research paper 57, 13, 2008). It is known that computing rc(G) is NP-Hard (Chakraborty and fischer in J Comb Optim 1–18, 2009). Here, we present a (r + 3)-factor approximation algorithm which runs in O(nm) time and a (d + 3)-factor approximation algorithm which runs in O(dm) time to rainbow colour any connected graph G on n vertices, with m edges, diameter d and radius r.