Cycles containing all vertices of maximum degree

For a graph G and an integer k, denote by V_k the set {v ∈ V(G) | d(v) ≥ k}. Veldman proved that if G is a 2-connected graph of order n with n ≤ 3k - 2 and |V_k| ≤ k, then G has a cycle containing all vertices of V_k. It is shown that the upper bound k on |V_k| is close to best possible in general. For the special case k = δ(G), it is conjectured that the condition |V_k| ≤ k can be omitted. Using a variation of Woodall's Hopping Lemma, the conjecture is proved under the additional condition that n ≤ 2δ(G) + δ(G) + 1. This result is an almost-generalization of Jackson's Theorem that every 2-connected k-regular graph of order n with n ≤ 3k is hamiltonian. An alternative proof of an extension of Jackson's Theorem is also presented. © 1993 John Wiley & Sons, Inc.     

The symmetric (2k,k)‐graphs

A noncomplete graph G is called an (n, k)‐graph if it is n‐connected and G − X is not (n − |X| + 1)‐connected for any X ⊆ V(G) with |X| ≤ k. Mader conjectured that for k ≥ 3 the graph K_{2k + 2} − (1‐factor) is the unique (2k, k)‐graph. We settle this conjecture for strongly regular graphs, for edge transitive graphs, and for vertex transitive graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 36: 35–51, 2001     

Centers to centroids in graphs

For S ? V(G) the S-center and S-centroid of G are defined as the collection of vertices u ∈ V(G) that minimize e_s(u) = max {d(u, v): v ∈ S} and d_s(u) = ∑_u∈S d(u, v), respectively. This generalizes the standard definition of center and centroid from the special case of S = V(G). For 1 ? k ?|V(G)| and u ∈ V(G) let r_k(u) = max {∑_s∈S d(u, s): S ? V(G), |S| = k}. The k-centrum of G, denoted C(G; k), is defined to be the subset of vertices u in G for which r_k(u) is a minimum. This also generalizes the standard definitions of center and centroid since C(G; 1) is the center and C(G; |V(G)|) is the centroid. In this paper the structure of these sets for trees is examined. Generalizations of theorems of Jordan and Zelinka are included.     

Brooks-type theorems for choosability with separation

We consider the following type of problems. Given a graph G = (V, E) and lists L(v) of allowed colors for its vertices v ∈ V such that |L(v)| = p for all v ∈ V and |L(u) ∩ L(v)| ≤ c for all uv ∈ E, is it possible to find a “list coloring,” i.e., a color f(v) ∈ L(v) for each v ∈ V, so that f(u) ≠ f(v) for all uv ∈ E? We prove that every of maximum degree Δ admits a list coloring for every such list assignment, provided p ≥ . Apart from a multiplicative constant, the result is tight, as lists of length may be necessary. Moreover, for G = K_n (the complete graph on n vertices) and c = 1 (i.e., almost disjoint lists), the smallest value of p is shown to have asymptotics (1 + o(1)) . For planar graphs and c = 1, lists of length 4 suffice. ˜© 1998 John Wiley & Sons, Inc. J Graph Theory 27: 43–49, 1998     

THE SECOND EXPONENT SET OF PRIMITIVE DIGRAPHS

51.IntroductionandNotationsLetD=(V,E)beadigraphandL(D)denotethesetofcyclelengthsofD.ForuEVandintegeri21,letfo(u):={vEVIthereedestsadirectedwalkoflengthifromutov}.WedelveRo(u):={u}.Letu,vEV.IfN (v)=N (v)andN--(v)=N--(v),thenwecanvacopyofu.LotDbeaprimitivedigraphand7(D)denotetheexponentofD.In1950,H.WielandtI61foundthat7(D)5(n--1)' 1andshowedthatthereisapiquedigraphthatattainsthisbound.In1964,A.L.DulmageandN.S.Mendelsohn[2]ObservedthattherearegapsintheexponentsetEd={ry(D)IDEPD.}…     

On 2‐factors of a bipartite graph

In this article, we consider the following problem: Given a bipartite graph G and a positive integer k, when does G have a 2‐factor with exactly k components? We will prove that if G = (V₁, V₂, E) is a bipartite graph with |V₁| = |V₂| = n ≥ 2k + 1 and δ (G) ≥ ⌈n/2⌉ + 1, then G contains a 2‐factor with exactly k components. We conjecture that if G = (V₁, V₂; E) is a bipartite graph such that |V₁| = |V₂| = n ≥ 2 and δ (G) ≥ ⌈n/2⌉ + 1, then, for any bipartite graph H = (U₁, U₂; F) with |U₁| ≤ n, |U₂| ≤ n and Δ (H) ≤ 2, G contains a subgraph isomorphic to H. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 101–106, 1999     

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     

Degree bounds for the circumference of 3‐connected graphs

Let C be a longest cycle in the 3‐connected graph G and let H be a component of G ? V(C) such that |V(H)| ≥ 3. We supply estimates of the form |C| ≥ 2d(u) + 2d(v) ? α(4 ≤ α ≤ 8), where u,v are suitably chosen non‐adjacent vertices in G. Also the exceptional classes for α = 6,7,8 are characterized. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Existence and Uniqueness of Strong Solutions for a Class of Quasi‐Linear Hyperbolic Equations with Order Degeneration

Let k(y) > 0, 𝓁(y) > 0 for y > 0, k(0) = 𝓁(0) = 0 and lim_{y → 0}k(y)/𝓁(y) exists; then the equation L(u) ≔ k(y)u_xx – ∂_y(𝓁(y)u_y) + a(x, y)u_x = f(x, y, u) is strictly hyperbolic for y > 0 and its order degenerates on the line y = 0. Consider the boundary value problem Lu = f(x, y, u) in G, u|_AC = 0, where G is a simply connected domain in ℝ² with piecewise smooth boundary ∂G = AB∪AC∪BC; AB = {(x, 0) : 0 ≤ x ≤ 1}, AC : x = F(y) = ∫^y₀(k(t)/𝓁(t))^1/2dt and BC : x = 1 – F(y) are characteristic curves. Existence of generalized solution is obtained by a finite element method, provided f(x, y, u) satisfies Carathéodory condition and |f(x, y, u)| ≤ Q(x, y) + b|u| with Q ∈ L²(G), b = const > 0. It is shown also that each generalized solution is a strong solution, and that fact is used to prove uniqueness under the additional assumption |f(x, y, u₁) – f(x, y, u₂| ≤ C|u₁ – u₂|, where C = const > 0.     

The <Emphasis Type="Italic">k</Emphasis>-point exponent set of primitive digraphs with girth 2

Let D = （V, E） be a primitive digraph. The vertex exponent of D at a vertex v∈ V, denoted by expD（v）, is the least integer p such that there is a v →u walk of length p for each u ∈ V. Following Brualdi and Liu, we order the vertices of D so that exPD（V1） ≤ exPD（V2） …≤ exPD（Vn）. Then exPD（Vk） is called the k- point exponent of D and is denoted by exPD （k）, 1≤ k ≤ n. In this paper we define e（n, k） ：= max{expD （k） ｜ D ∈ PD（n, 2）} and E（n, k） ：= {exPD（k）｜ D ∈ PD（n, 2）}, where PD（n, 2） is the set of all primitive digraphs of order n with girth 2. We completely determine e（n, k） and E（n, k） for all n, k with n ≥ 3 and 1 ≤ k ≤ n.     

A characterization of panconnected graphs satisfying a local ore-type condition

It is well known that a graph G of order p ≥ 3 is Hamilton-connected if d(u) + d(v) ≥ p + 1 for each pair of nonadjacent vertices u and v. In this paper we consider connected graphs G of order at least 3 for which d(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| + 1 for any path uwv with uv ∉ E(G), where N(x) denote the neighborhood of a vertex x. We prove that a graph G satisfying this condition has the following properties: (a) For each pair of nonadjacent vertices x, y of G and for each integer k, d(x, y) ≤ k ≤ |V(G)| − 1, there is an x − y path of length k. (b) For each edge xy of G and for each integer k (excepting maybe one k η {3,4}) there is a cycle of length k containing xy. Consequently G is panconnected (and also edge pancyclic) if and only if each edge of G belongs to a triangle and a quadrangle. Our results imply some results of Williamson, Faudree, and Schelp. © 1996 John Wiley & Sons, Inc.     

The partition dimension of circulant graphs

Let Π = {S₁, S₂, . . . , S_k} be an ordered partition of the vertex set V (G) of a graph G. The partition representation of a vertex v ∈ V (G) with respect to Π is the k-tuple r(v|Π) = (d(v, S₁), d(v, S₂), . . . , d(v, S_k)), where d(v, S) is the distance between v and a set S. If for every pair of distinct vertices u, v ∈ V (G), we have r(u|Π) ≠ r(v|Π), then Π is a resolving partition and the minimum cardinality of a resolving partition of V (G) is called the partition dimension of G. We study the partition dimension of circulant graphs, which are Cayley graphs of cyclic groups. Grigorious et al. [On the partition dimension of circulant graphs] proved that pd(C_n(1, 2, . . . , t)) ≥ t + 1 for n ≥ 3. We disprove this statement by showing that if t ≥ 4 is even, then there exists an infinite set of values of n, such that . We also present exact values of the partition dimension of circulant graphs with 3 generators.     

Independent sets in tensor graph powers

The tensor product of two graphs, G and H, has a vertex set V(G) × V(H) and an edge between (u,v) and (u′,v′) iff both u u′ ∈ E(G) and v v′ ∈ E(H). Let A(G) denote the limit of the independence ratios of tensor powers of G, lim, α(Gⁿ)/|V(Gⁿ)|. This parameter was introduced in [Brown, Nowakowski, Rall, SIAM J Discrete Math 9 ( 5 ), 290–300], where it was shown that A(G) is lower bounded by the vertex expansion ratio of independent sets of G. In this article we study the relation between these parameters further, and ask whether they are in fact equal. We present several families of graphs where equality holds, and discuss the effect the above question has on various open problems related to tensor graph products. © 2006 Wiley Periodicals, Inc. J Graph Theory     

The average Steiner distance of a graph

The average distance μ(G) of a graph G is the average among the distances between all pairs of vertices in G. For n ≥ 2, the average Steiner n-distance μ_n(G) of a connected graph G is the average Steiner distance over all sets of n vertices in G. It is shown that for a connected weighted graph G, μ_n(G) ≤ μ_k(G) + μ_n+1−k(G) where 2 ≤ k ≤ n − 1. The range for the average Steiner n-distance of a connected graph G in terms of n and |V(G)| is established. Moreover, for a tree T and integer k, 2 ≤ k ≤ n − 1, it is shown that μ_n(T) ≤ (n/k)μ_k(T) and the range for μ_n(T) in terms of n and |V(T)| is established. Two efficient algorithms for finding the average Steiner n-distance of a tree are outlined. © 1996 John Wiley & Sons, Inc.     

On packing 3‐vertex paths in a graph

Let G be a connected graph and let eb(G) and λ(G) denote the number of end‐blocks and the maximum number of disjoint 3‐vertex paths Λ in G. We prove the following theorems on claw‐free graphs: (t1) if G is claw‐free and eb(G) ≤ 2 (and in particular, G is 2‐connected) then λ(G) = ⌊| V(G)|/3⌋; (t2) if G is claw‐free and eb(G) ≥ 2 then λ(G) ≥ ⌊(| V(G) | − eb(G) + 2)/3 ⌋; and (t3) if G is claw‐free and Δ^*‐free then λ(G) = ⌊| V(G) |/3⌋ (here Δ^* is a graph obtained from a triangle Δ by attaching to each vertex a new dangling edge). We also give the following sufficient condition for a graph to have a Λ‐factor: Let n and p be integers, 1 ≤ p ≤ n − 2, G a 2‐connected graph, and |V(G)| = 3n. Suppose that G − S has a Λ‐factor for every S ⊆ V(G) such that |S| = 3p and both V(G) − S and S induce connected subgraphs in G. Then G has a Λ‐factor. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 175–197, 2001     

Acyclic 5‐choosability of planar graphs without small cycles

A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L = {L(v): v: ∈ V}, there exists a proper acyclic coloring ? of G such that ?(v) ∈ L(v) for all v ∈ V. If G is acyclically L‐list colorable for any list assignment with |L (v)|≥ k for all v ∈ V, then G is acyclically k‐choosable. In this article, we prove that every planar graph G without 4‐ and 5‐cycles, or without 4‐ and 6‐cycles is acyclically 5‐choosable. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 245–260, 2007     

Spanning k-Trees of n-Connected Graphs

A tree is called a k-tree if the maximum degree is at most k. We prove the following theorem, by which a closure concept for spanning k-trees of n-connected graphs can be defined. Let k ≥ 2 and n ≥ 1 be integers, and let u and v be a pair of nonadjacent vertices of an n-connected graph G such that deg _G (u) + deg _G (v) ≥ |G| − 1 − (k − 2)n, where |G| denotes the order of G. Then G has a spanning k-tree if and only if G + uv has a spanning k-tree.     

Bipartite labeling of trees with maximum degree three

Let T = (V, E) be a tree with a properly 2‐colored vertex set. A bipartite labeling of T is a bijection φ: V → {1, …, |V|} for which there exists a k such that whenever φ(u) ≤ k < φ(v), then u and v have different colors. The α‐size α(T) of the tree T is the maximum number of elements in the sets {|φ(u) − φ(v)|; uv ∈ E}, taken over all bipartite labelings φ of T. The quantity α(n) is defined as the minimum of α(T) over all trees with n vertices. In an earlier article (J Graph Theory 19 (1995), 201–215), A. Rosa and the second author proved that 5n/7 ≤ α(n) ≤ (5n + 4)/6 for all n ≥ 4; the upper bound is believed to be the asymptotically correct value of (n). In this article, we investigate the α‐size of trees with maximum degree three. Let α₃(n) be the smallest α‐size among all trees with n vertices, each of degree at most three. We prove that α₃(n) ≥ 5n/6 for all n ≥ 12, thus supporting the belief above. This result can be seen as an approximation toward the graceful tree conjecture—it shows that every tree on n ≥ 12 vertices and with maximum degree three has “gracesize” at least 5n/6. Using a computer search, we also establish that α₃(n) ≥ n − 2 for all n ≤ 17. © 1999 John Wiley & Sons, Inc. J Graph Theory 31:7–15, 1999     

On the acyclic choosability of graphs

A proper vertex coloring of a graph G = (V,E) is acyclic if G contains no bicolored cycle. A graph G is L‐list colorable if for a given list assignment L = {L(v): v ∈ V}, there exists a proper coloring c of G such that c (v) ∈ L(v) for all v ∈ V. If G is L‐list colorable for every list assignment with |L (v)| ≥ k for all v ∈ V, then G is said k‐choosable. A graph is said to be acyclically k‐choosable if the obtained coloring is acyclic. In this paper, we study the links between acyclic k‐choosability of G and Mad(G) defined as the maximum average degree of the subgraphs of G and give some observations about the relationship between acyclic coloring, choosability, and acyclic choosability. © 2005 Wiley Periodicals, Inc. J Graph Theory 51: 281–300, 2006