NEIGHBORHOOD UNION OF INDEPENDENT SETS AND HAMILTONICITY OF CLAW-FREE GRAPHS

Let G be a graph,for any u∈V(G),let N(u) denote the neighborhood of u and d(u)=|N(u)| be the degree of u. For any U V(G) ,let N(U)=Uu,∈UN(u), and d(U)=|N(U)|.A graph G is called claw-free if it has no induced subgraph isomorphic to K1.3. One of the fundamental results concerning cycles in claw-free graphs is due to Tian Feng,et al. : Let G be a 2-connected claw-free graph of order n,and d(u) d(v) d(w)≥n-2 for every independent vertex set {u,v,w} of G, then G is Hamiltonian. It is proved that, for any three positive integers s ,t and w,such that if G is a (s t w-1)connected claw-free graph of order n,and d(S) d(T) d(W)＞n-(s t w) for every three disjoint independent vertex sets S,T,W with |S |=s, |T|=t, |W|=w,and S∪T∪W is also independent ,then G is Hamiltonian. Other related results are obtained too.     

Bounds on a generalized domination parameter

Abstract

If n is an integer, n ≥ 2 and u and v are vertices of a graph G, then u and v are said to be K_n-adjacent vertices of G if there is a subgraph of G, isomorphic to K_n , containing u and v. For n ≥ 2, a K_n- dominating set of G is a set D of vertices such that every vertex of G belongs to D or is K_n-adjacent to a vertex of D. The K_n-domination number γK_n (G) of G is the minimum cardinality among the K_n-dominating sets of vertices of G. It is shown that, for n ε {3,4}, if G is a graph of order p with no K_n-isolated vertex, then γK_n (G) ≤ p/n. We establish that this is a best possible upper bound. It is shown that the result is not true for n ≥ 5.     

Graphs characterized by the second eigenvalue

In this paper we prove that for a simple graph G without isolated vertices 0 < λ₂(G) < 1/3 if and only if G ? K?_n-3 V (K₁ ∪ K₂), the graph obtained by joining each vertex of K?_n-3 to each vertex of K₁ ∪ K₂). © 1993 John Wiley & Sons, Inc.     

The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.     

Spanning 2‐trails from degree sum conditions

Suppose G is a simple connected n‐vertex graph. Let σ₃(G) denote the minimum degree sum of three independent vertices in G (which is ∞ if G has no set of three independent vertices). A 2‐trail is a trail that uses every vertex at most twice. Spanning 2‐trails generalize hamilton paths and cycles. We prove three main results. First, if σ₃G)≥ n ‐ 1, then G has a spanning 2‐trail, unless G ? K_1,3. Second, if σ₃(G) ≥ n, then G has either a hamilton path or a closed spanning 2‐trail. Third, if G is 2‐edge‐connected and σ₃(G) ≥ n, then G has a closed spanning 2‐trail, unless G ? K_2,3 or K (the 6‐vertex graph obtained from K_2,3 by subdividing one edge). All three results are sharp. These results are related to the study of connected and 2‐edge‐connected factors, spanning k‐walks, even factors, and supereulerian graphs. In particular, a closed spanning 2‐trail may be regarded as a connected (and 2‐edge‐connected) even [2,4]‐factor. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 298–319, 2004     

Euler Tours of Maximum Girth in K2 n +1 and K2 n ,2 n

Given an eulerian graph G and an Euler tour T of G, the girth of T, denoted by g(T), is the minimum integer k such that some segment of k+1 consecutive vertices of T is a cycle of length k in G. Let g^E(G)= maxg(T) where the maximum is taken over all Euler tours of G.We prove that g^E(K_2n,2n)=4n–4 and 2n–3g^E(K_2n+1)2n–1 for any n2. We also show that g^E(K₇)=4. We use these results to prove the following:1)The graph K_2n,2n can be decomposed into edge disjoint paths of length k if and only if k4n–1 and the number of edges in K_2n,2n is divisible by k.2)The graph K_2n+1 can be decomposed into edge disjoint paths of length k if and only if k2n and the number edges in K_2n+1 is divisible by k.     

Note on the cochromatic number of several surfaces

The cochromatic number of a graph G, denoted by z(G), is the minimum number of subsets into which the vertex set of G can be partitioned so that each subset induces an empty or a complete subgraph of G. In an earlier work, the author considered the problem of determining z(S), the maximum cochromatic number among all graphs that embed in a surface S. The value of z(S) was found for the sphere, the Klein bottle, and for the nonorientable surface of genus 4. In this note, some recent results of Albertson and Hutchinson are used to determine the cochromatic numbers of the projective plane and the nonorientable surface of genus 3. These results lend further evidence to support the conjecture that z(S) is equal to the maximum n for which the graph G_n = K₁ U K₂ U … U K_n embeds in S.     

Trees with Equal Domination and Restrained Domination Numbers

Let G = (V,E) be a graph and let S V. The set S is a packing in G if the vertices of S are pairwise at distance at least three apart in G. The set S is a dominating set (DS) if every vertex in V − S is adjacent to a vertex in S. Further, if every vertex in V − S is also adjacent to a vertex in V − S, then S is a restrained dominating set (RDS). The domination number of G, denoted by γ(G), is the minimum cardinality of a DS of G, while the restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of a RDS of G. The graph G is γ-excellent if every vertex of G belongs to some minimum DS of G. A constructive characterization of trees with equal domination and restrained domination numbers is presented. As a consequence of this characterization we show that the following statements are equivalent: (i) T is a tree with γ(T)=γ_r(T); (ii) T is a γ-excellent tree and T ≠ K₂; and (iii) T is a tree that has a unique maximum packing and this set is a dominating set of T. We show that if T is a tree of order n with ℓ leaves, then γ_r(T) ≤ (n + ℓ + 1)/2, and we characterize those trees achieving equality.     

Combinatorial interpretations for TG(1, −1)

Let G be a connected and simple graph with vertex set {1, 2, …, n + 1} and T_G(x, y) the Tutte polynomial of G. In this paper, we give combinatorial interpretations for T_G(1, ?1). In particular, we give the definitions of even spanning tree and left spanning tree. We prove T_G(1, ?1) is the number of even‐left spanning trees of G. We associate a permutation with a spanning forest of G and give the definition of odd G‐permutations. We show T_G(1, ?1) is the number of odd G‐permutations. We give a bijection from the set of odd K_{n + 1}‐permutations to the set of alternating permutations on the set {1, 2, …, n}. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 341–348, 2012     

Claw‐decompositions and tutte‐orientations

We conjecture that, for each tree T, there exists a natural number k_T such that the following holds: If G is a k_T‐edge‐connected graph such that |E(T)| divides |E(G)|, then the edges of G can be divided into parts, each of which is isomorphic to T. We prove that for T = K_1,3 (the claw), this holds if and only if there exists a (smallest) natural number k_t such that every k_t‐edge‐connected graph has an orientation for which the indegree of each vertex equals its outdegree modulo 3. Tutte's 3‐flow conjecture says that k_t = 4. We prove the weaker statement that every 4$\lceil$ log n$\rceil$ ‐edge‐connected graph with n vertices has an edge‐decomposition into claws provided its number of edges is divisible by 3. We also prove that every triangulation of a surface has an edge‐decomposition into claws. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 135–146, 2006     

Thep-intersection number of a complete bipartite graph and orthogonal double coverings of a clique

Thep-intersection graph of a collection of finite sets {S _i } _i=1 ⁿ is the graph with vertices 1, ...,n such thati, j are adjacent if and only if |S _i S _j |p. Thep-intersection number of a graphG, herein denoted _p (G), is the minimum size of a setU such thatG is thep-intersection graph of subsets ofU. IfG is the complete bipartite graphK _n,n andp2, then _p (K _{n, n} )(n ²+(2p–1)n)/p. Whenp=2, equality holds if and only ifK _n has anorthogonal double covering, which is a collection ofn subgraphs ofK _n , each withn–1 edges and maximum degree 2, such that each pair of subgraphs shares exactly one edge. By construction,K _n has a simple explicit orthogonal double covering whenn is congruent modulo 12 to one of {1, 2, 5, 7, 10, 11}.Research supported in part by ONR Grant N00014-5K0570.     

The 2-intersection number of paths and bounded-degree trees

We represent a graph by assigning each vertex a finite set such that vertices are adjacent if and only if the corresponding sets have at least two common elements. The 2-intersection number θ₂(G) of a graph G is the minimum size of the union of sets in such a representation. We prove that the maximum order of a path that can be represented in this way using t elements is between (t² - 19t + 4)/4 and (t² - t + 6)/4, making θ₂(P_n) asymptotic to 2√n. We also show the existence of a constant c depending on ? such that, for any tree T with maximum degree at most d, θ₂(T) ≤ c(√n)^1+?. When the maximum degree is not bounded, there is an n-vertex tree T with θ₂(T) > .945n^2/3. © 1995 John Wiley & Sons, Inc.     

Maximum hitting time for random walks on graphs

For x and y vertices of a connected graph G, let T_G(x, y) denote the expected time before a random walk starting from x reaches y. We determine, for each n > 0, the n-vertex graph G and vertices x and y for which T_G(x, y) is maximized. the extremal graph consists of a clique on ?(2n + 1)/3?) (or ?)(2_n ? 2)/3?) vertices, including x, to which a path on the remaining vertices, ending in y, has been attached; the expected time T_G(x, y) to reach y from x in this graph is approximately 4_n³/27.     

Overlap number of graphs

An overlap representation of a graph G assigns sets to vertices so that vertices are adjacent if and only if their assigned sets intersect with neither containing the other. The overlap number φ(G) (introduced by Rosgen) is the minimum size of the union of the sets in such a representation. We prove the following: (1) An optimal overlap representation of a tree can be produced in linear time, and its size is the number of vertices in the largest subtree in which the neighbor of any leaf has degree 2. (2) If δ(G)?2 and G≠K₃, then φ(G)?|E(G)| ? 1, with equality when G is connected and triangle‐free and has no star‐cutset. (3) If G is an n‐vertex plane graph with n?5, then φ(G)?2n ? 5, with equality when every face has length 4 and there is no star‐cutset. (4) If G is an n‐vertex graph with n?14, then φ(G)?n²/4 ? n/2 ? 1, with equality for even n when G arises from K_{n/2, n/2} by deleting a perfect matching. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Some arrowing results for trees versus complete graphs

For an arbitrary tree T of order m and an arbitrary positive integer n, Chvátal proved that the Ramsey number r(T, K_n) = 1 + (m ? 1) (n ? 1). for graphs G, G₁, and G₂, we say that G arrows G₁ and G₂, written G → (G₁, G₂), if for every factorization G = R ⊕ B, either G₁ is a subgraph of R or G₂ is a subgraph of B. it is shown that (i) for each l ≥ 2, K₁+ (m?1)(n?1) ?E(K₁) → (T, K_n) for m ≥ 2/ ? 1 and n ≥ 2; (ii) K₁ +,(m ?1)(n ?1) ? E(H) → (T, K_n), where H is any tree of order m ? 1, m ≥ 3 and n ≥ 2. It is further shown that result (i) is sharp with respect to the inequality m ≥ 2/? 1; in particular, examples are given to show that K1 + (2l?3)(n?1) E(K₁) ? (P_21?2, K_n) for all n ≥ 2, where P_21?2 denotes the path of order 21 ? 2. Also result (ii) is sharp with respect to the order of H; examples aregiven to show that K₁ + _(m?1)(n?1)? E(K(1, m ? 1)) ?(T, K_n)for any tree T of order m and any n ≥ 2.     

Some panconnected and pancyclic properties of graphs with a local ore-type condition

Asratian and Khachatrian proved that a connected graphG of order at least 3 is hamiltonian ifd(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| for any pathuwv withuv ? E(G), whereN(x) is the neighborhood of a vertexx. We prove that a graphG with this condition, which is not complete bipartite, has the following properties:

1. For each pair of verticesx, y with distanced(x, y) ≥ 3 and for each integern, d(x, y) ≤ n ≤ |V(G)| ? 1, there is anx ? y path of lengthn.
2. For each edgee which does not lie on a triangle and for eachn, 4 ≤ n ≤ |V(G)|, there is a cycle of lengthn containinge.
3. Each vertex ofG lies on a cycle of every length from 4 to |V(G)|.

This implies thatG is vertex pancyclic if and only if each vertex ofG lies on a triangle.     

Isoperimetric numbers of graph bundles

The main aim of this paper is to give some upper and lower bounds for the isoperimetric numbers of graph coverings or graph bundles, with exact values in some special cases. In addition, we show that the isoperimetric number of any covering graph is not greater than that of the base graph. Mohar's theorem for the isoperimetric number of the cartesian product of a graph and a complete graph can be extended to a more general case: The isoperimetric numberi(G × K _2n) of the cartesian product of any graphG and a complete graphK _2n on even vertices is the minimum of the isoperimetric numberi(G) andn, and it is also a sharp lower bound of the isoperimetric numbers of all graph bundles over the graphG with fiberK _2n. Furthermore, ifn 2i(G) then the isoperimetric number of any graph bundle overG with fibreK _n is equal to the isoperimetric numberi(G) ofG. Partially supported by The Ministry of Education, Korea.     

A short proof of a theorem on Hamiltonian graphs

In this note, we give a short proof of a stronger version of the following theorem: Let G be a 2-connected graph of order n such that $ d(u)+d(v)+d(w) \geq n + \mid N(u) \cap N(v) \cap N(w) \mid $ for any independent set {u, v, w}, then G is hamiltonian. © 1996 John Wiley & Sons Inc.     

ON A CONJECTURE ON nTH ORDER DEGREE REGULAR GRAPHS

Abstract

For n a positive integer and v a vertex of a graph G, the nth order degree of v in G, denoted by deg_nv, is the number of vertices at distance n from v. The graph G is said to be nth order regular of degree k if, for every vertex v of G, deg_nv = k. The following conjecture due to Alavi, Lick, and Zou is proved: For n ≥ 2, if G is a connected nth order regular graph of degree 1, then G is either a path of length 2n—1 or G has diameter n. Properties of nth order regular graphs of degree k, k ≥ 1, are investigated.     

Proof of a tiling conjecture of Komlós

A conjecture of Komlós states that for every graph H, there is a constant K such that if G is any n‐vertex graph of minimum degree at least (1 ? (1/χ_cr(H)))n, where χ_cr(H) denotes the critical chromatic number of H, then G contains an H‐matching that covers all but at most K vertices of G. In this paper we prove that the conjecture holds for all sufficiently large values of n. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 180–205, 2003