Edge disjoint Hamilton cycles in graphs

Let G be a graph of order n and k ≥ 0 an integer. It is conjectured in [8] that if for any two vertices u and v of a 2(k + 1)‐connected graph G,d _G (u,v) = 2 implies that max{d(u;G), d(v;G)} ≥ (n/2) + 2k, then G has k + 1 edge disjoint Hamilton cycles. This conjecture is true for k = 0, 1 (see cf. [3] and [8]). It will be proved in this paper that the conjecture is true for every integer k ≥ 0. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 8–20, 2000     

[a,b]-factorizations of graphs

Let a and b be integers with b ? a ? 0. A graph G is called an [a,b]-graph if a ? d_G(v) ? b for each vertex v ∈ V(G), and an [a,b]-factor of a graph G is a spanning [a,b]-subgraph of G. A graph is [a,b]-factorable if its edges can be decomposed into [a,b]-factors. The purpose of this paper is to prove the following three theorems: (i) if 1 ? b ? 2a, every [(12a + 2)m + 2an,(12b + 4)m + 2bn]-graph is [2a, 2b + 1]-factorable; (ii) if b ? 2a ?1, every [(12a ?4)m + 2an, (12b ?2)m + 2bn]-graph is [2a ?1,2b]-factorable; and (iii) if b ? 2a ?1, every [(6a ?2)m + 2an, (6b + 2)m + 2bn]-graph is [2a ?1,2b + 1]-factorable, where m and n are nonnegative integers. They generalize some [a,b]-factorization results of Akiyama and Kano [3], Kano [6], and Era [5].     

Partitions of a graph into paths with prescribed endvertices and lengths

For a graph G, let σ₂(G) denote the minimum degree sum of a pair of nonadjacent vertices. We conjecture that if |V(G)| = n = Σ^k_{i = 1} a_i and σ₂(G) ≥ n + k − 1, then for any k vertices v₁, v₂,…, v_k in G, there exist vertex‐disjoint paths P₁, P₂,…, P_k such that |V(P_i)| = a_i and v_i is an endvertex of P_i for 1 ≤ i ≤ k. In this paper, we verify the conjecture for the cases where almost all a_i ≤ 5, and the cases where k ≤ 3. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 163–169, 2000     

[a,b]-factorization of a graph

Let a and b be integers such that 0 ? a ? b. Then a graph G is called an [a, b]-graph if a ? d_G(x) ? b for every x ? V(G), and an [a, b]-factor of a graph is defined to be its spanning subgraph F such that a ? d_F(x) ? b for every vertex x, where d_G(x) and d_F(x) denote the degrees of x in G and F, respectively. If the edges of a graph can be decomposed into [a.b]-factors then we say that the graph is [2a, 2a]-factorable. We prove the following two theorems: (i) a graph G is [2a, 2b)-factorable if and only if G is a [2am,2bm]-graph for some integer m, and (ii) every [8m + 2k, 10m + 2k]-graph is [1,2]-factorable.     

Long cycles passing through a specified path in a graph

For a graph G and an integer k ≥ 1, let ς_k(G) = d_G(v_i): {v₁, …, v_k} is an independent set of vertices in G}. Enomoto proved the following theorem. Let s ≥ 1 and let G be a (s + 2)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, ς₂(G) − s} passing through any path of length s. We generalize this result as follows. Let k ≥ 3 and s ≥ 1 and let G be a (k + s − 1)-connected graph. Then G has a cycle of length ≥ min{|V(G)|, − s} passing through any path of length s. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 177–184, 1998     

Degree conditions for k‐ordered hamiltonian graphs

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. It is shown that if G is a graph of order n with 3 ≤ k ≤ n/2, and deg(u) + deg(v) ≥ n + (3k − 9)/2 for every pair u, v of nonadjacent vertices of G, then G is k-ordered hamiltonian. Minimum degree conditions are also given for k-ordered hamiltonicity. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 199–210, 2003     

The Sigma Chromatic Number of a Graph

For a nontrivial connected graph G, let ${c: V(G)\to {{\mathbb N}}}For a nontrivial connected graph G, let c: V(G)? \mathbb N{c: V(G)\to {{\mathbb N}}} be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.     

A note on the weakly convex and convex domination numbers of a torus

The distanced_G(u,v) between two vertices u and v in a connected graph G is the length of the shortest (u,v) path in G. A (u,v) path of length d_G(u,v) is called a (u,v)-geodesic. A set X⊆V is called weakly convex in G if for every two vertices a,b∈X, exists an (a,b)-geodesic, all of whose vertices belong to X. A set X is convex in G if for all a,b∈X all vertices from every (a,b)-geodesic belong to X. The weakly convex domination number of a graph G is the minimum cardinality of a weakly convex dominating set of G, while the convex domination number of a graph G is the minimum cardinality of a convex dominating set of G. In this paper we consider weakly convex and convex domination numbers of tori.     

Some reproducing identities for families of mean values

Gini, Lehmer, Beckenbach, and others studied the meanG _s (a, b) = (a ^s +b ^s )/(a ^{s 1} +b ^s-1 ) We proveTheorem 1 The identity (ina, b)G _s (G _t ,G _u ) =G _v holds if and only if (s, t, u, v) is (s, t, t, t) (the trivial solution) or one of (1, 1 –k, 1 +k, 1), (1/2, 1 –k, k, 1/2), or (0,–k, k, 0) (the exotic solutions,k is any real number)Theorem 2 IfP _s (a, b) is the power mean [(a ^s +b ^s )/2]^1/s , thenP _s (P _t ,P _u ) =P _v has only the trivial solution (s, t, u, v) = (s, t, t, t) and the exotic solution (0,t, –t, 0) The family of meansG _s (respP _s ) includes the classical arithmetic, geometric, and harmonic means     

On low bound of degree sequences of spanning trees in K-edge-connected graphs

A graph G = (V, E) is k-edge-connected if for any subset E′ ⊆ E,|E′| < k, G − E′ is connected. A d_k-tree T of a connected graph G = (V, E) is a spanning tree satisfying that ∀v ∈ V, d_T(v) ≤ + α, where [·] is a lower integer form and α depends on k. We show that every k-edge-connected graph with k ≥ 2, has a d_k-tree, and α = 1 for k = 2, α = 2 for k ≥ 3. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 87–95, 1998     

Edge‐face chromatic number and edge chromatic number of simple plane graphs

Given a simple plane graph G, an edge‐face k‐coloring of G is a function ? : E(G) ∪ F(G) → {1,…,k} such that, for any two adjacent or incident elements a, b ∈ E(G) ∪ F(G), ?(a) ≠ ?(b). Let χ_e(G), χ_ef(G), and Δ(G) denote the edge chromatic number, the edge‐face chromatic number, and the maximum degree of G, respectively. In this paper, we prove that χ_ef(G) = χ_e(G) = Δ(G) for any 2‐connected simple plane graph G with Δ (G) ≥ 24. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Efficient algorithms for decomposing graphs under degree constraints

Stiebitz [Decomposing graphs under degree constraints, J. Graph Theory 23 (1996) 321-324] proved that if every vertex v in a graph G has degree d(v)?a(v)+b(v)+1 (where a and b are arbitrarily given nonnegative integer-valued functions) then G has a nontrivial vertex partition (A,B) such that d_A(v)?a(v) for every v∈A and d_B(v)?b(v) for every v∈B. Kaneko [On decomposition of triangle-free graphs under degree constraints, J. Graph Theory 27 (1998) 7-9] and Diwan [Decomposing graphs with girth at least five under degree constraints, J. Graph Theory 33 (2000) 237-239] strengthened this result, proving that it suffices to assume d(v)?a+b (a,b?1) or just d(v)?a+b-1 (a,b?2) if G contains no cycles shorter than 4 or 5, respectively.The original proofs contain nonconstructive steps. In this paper we give polynomial-time algorithms that find such partitions. Constructive generalizations for k-partitions are also presented.     

{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.     

Graph decompositions without isolated vertices III

Let G be a graph of order n, and n = Σ^k_i=1 a_i be a partition of n with a_i ≥ 2. In this article we show that if the minimum degree of G is at least 3k−2, then for any distinct k vertices v₁,…, v_k of G, the vertex set V(G) can be decomposed into k disjoint subsets A₁,…, A_k so that |A_i| = a_i,v_iisA_i is an element of A_i and “the subgraph induced by A_i contains no isolated vertices” for all i, 1 ≥ i ≥ k. Here, the bound on the minimum degree is sharp. © 1997 John Wiley & Sons, Inc.     

On Spanning Disjoint Paths in Line Graphs

Spanning connectivity of graphs has been intensively investigated in the study of interconnection networks (Hsu and Lin, Graph Theory and Interconnection Networks, 2009). 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, 2012). In Catlin and Lai (Graph Theory, Combinatorics, and Applications, vol. 1, pp. 207–222, 1991) 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}.     

Two‐factors each component of which contains a specified vertex

It is shown that if G is a graph of order n with minimum degree δ(G), then for any set of k specified vertices {v₁,v₂,…,v_k} ? V(G), there is a 2‐factor of G with precisely k cycles {C₁,C₂,…,C_k} such that v_i ∈ V(C_i) for (1 ≤ i ≤ k) if or 3k + 1 ≤ n ≤ 4k, or 4k ≤ n ≤ 6k ? 3,δ(G) ≥ 3k ? 1 or n ≥ 6k ? 3, . Examples are described that indicate this result is sharp. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 188–198, 2003     

Closure, 2-factors,and cycle coverings in claw-free graphs

In this article, we study cycle coverings and 2-factors of a claw-free graph and those of its closure, which has been defined by the first author (On a closure concept in claw-free graphs, J Combin Theory Ser B 70 (1997), 217–224). For a claw-free graph G and its closure cl(G), we prove: (1) V(G) is covered by k cycles in G if and only if V(cl(G)) is covered by k cycles of cl(G); and (2) G has a 2-factor with at most k components if and only if cl(G) has a 2-factor with at most k components. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 109–117, 1999     

k-ordered Hamiltonian graphs

A hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Theorems by Dirac and Ore, presenting sufficient conditions for a graph to be hamiltonian, are generalized to k-ordered hamiltonian graphs. The existence of k-ordered graphs with small maximum degree is investigated; in particular, a family of 4-regular 4-ordered graphs is described. A graph G of order n ≥ 3 is k-hamiltonian-connected, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices, G contains a v₁-v_k hamiltonian path that encounters v₁, v₂,…, v_k in this order. It is shown that for k ≥ 3, every (k + 1)-hamiltonian-connected graph is k-ordered and a result of Ore on hamiltonian-connected graphs is generalized to k-hamiltonian-connected graphs. © 1997 John Wiley & Sons, Inc.     

Some results on generalized exponents

A digraph G = (V, E) is primitive if, for some positive integer k, there is a u → v walk of length k for every pair u, v of vertices of V. The minimum such k is called the exponent of G, denoted exp(G). The exponent of a vertex u ∈ V, denoted exp(u), is the least integer k such that there is a u → v walk of length k for each v ∈ V. For a set X ⊆ V, exp(X) is the least integer k such that for each v ∈ V there is a X → v walk of length k, i.e., a u → v walk of length k for some u ∈ X. Let F(G, k) : = max{exp(X) : |X| = k} and F(n, k) : = max{F(G, k) : |V| = n}, where |X| and |V| denote the number of vertices in X and V, respectively. Recently, B. Liu and Q. Li proved F(n, k) = (n − k)(n − 1) + 1 for all 1 ≤ k ≤ n − 1. In this article, for each k, 1 ≤ k ≤ n − 1, we characterize the digraphs G such that F(G, k) = F(n, k), thereby answering a question of R. Brualdi and B. Liu. We also find some new upper bounds on the (ordinary) exponent of G in terms of the maximum outdegree of G, Δ⁺(G) = max{d⁺(u) : u ∈ V}, and thus obtain a new refinement of the Wielandt bound (n − 1)² + 1. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 215–225, 1998     

The adaptable choosability number grows with the choosability number

The adaptable choosability number of a multigraph G, denoted ch_a(G), is the smallest integer k such that every edge labeling of G and assignment of lists of size k to the vertices of G permits a list coloring of G in which no edge e=uv has both u and v colored with the label of e. We show that ch_a grows with ch, i.e. there is a function f tending to infinity such that ch_a(G)≥f(ch(G)).