Eulerian subgraphs in 3‐edge‐connected graphs and Hamiltonian line graphs

In this paper, we show that if G is a 3‐edge‐connected graph with and , then either G has an Eulerian subgraph H such that , or G can be contracted to the Petersen graph in such a way that the preimage of each vertex of the Petersen graph contains at least one vertex in S. If G is a 3‐edge‐connected planar graph, then for any , G has an Eulerian subgraph H such that . As an application, we obtain a new result on Hamiltonian line graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 308–319, 2003     

Upper total domination in claw‐free graphs

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S (other than itself). The maximum cardinality of a minimal total dominating set of G is the upper total domination number of G, denoted by Γ_t(G). We establish bounds on Γ_t(G) for claw‐free graphs G in terms of the number n of vertices and the minimum degree δ of G. We show that if if , and if δ ≥ 5. The extremal graphs are characterized. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 148–158, 2003     

Construction of graphs with given circular flow numbers

Suppose r ≥ 2 is a real number. A proper r‐flow of a directed multi‐graph is a mapping such that (i) for every edge , ; (ii) for every vertex , . The circular flow number of a graph G is the least r for which an orientation of G admits a proper r‐flow. The well‐known 5‐flow conjecture is equivalent to the statement that every bridgeless graph has circular flow number at most 5. In this paper, we prove that for any rational number r between 2 and 5, there exists a graph G with circular flow number r. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 304–318, 2003     

Circular choosability via combinatorial Nullstellensatz

A p‐list assignment L of a graph G assigns to each vertex v of G a set of permissible colors. We say G is L‐(P, q)‐colorable if G has a (P, q)‐coloring h such that h(v) ? L(v) for each vertex v. The circular list chromatic number of a graph G is the infimum of those real numbers t for which the following holds: For any P, q, for any P‐list assignment L with , G is L‐(P, q)‐colorable. We prove that if G has an orientation D which has no odd directed cycles, and L is a P‐list assignment of G such that for each vertex v, , then G is L‐(P, q)‐colorable. This implies that if G is a bipartite graph, then , where is the maximum average degree of a subgraph of G. We further prove that if G is a connected bipartite graph which is not a tree, then . © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 190–204, 2008     

Ore‐type degree conditions for a graph to be H‐linked

Given a fixed multigraph H with V(H) = {h₁,…, h_m}, we say that a graph G is H‐linked if for every choice of m vertices v₁, …, _vm in G, there exists a subdivision of H in G such that for every i, v_i is the branch vertex representing h_i. This generalizes the notion of k‐linked graphs (as well as some other notions). For a family of graphs, a graph G is ‐linked if G is H‐linked for every . In this article, we estimate the minimum integer r = r(n, k, d) such that each n‐vertex graph with is ‐linked, where is the family of simple graphs with k edges and minimum degree at least . © 2008 Wiley Periodicals, Inc. J Graph Theory 58: 14–26, 2008     

Small degree out‐branchings

Using a suitable orientation, we give a short proof of a strengthening of a result of Czumaj and Strothmann 4 : Every 2‐edge‐connected graph G contains a spanning tree T with the property that for every vertex v. As an analogue of this result in the directed case, we prove that every 2‐arc‐strong digraph D has an out‐branching B such that . A corollary of this is that every k‐arc‐strong digraph D has an out‐branching B such that , where . We conjecture that in this case would be the right (and best possible) answer. If true, this would again imply a strengthening of a result from 4 concerning spanning trees with small degrees in k‐connected graphs when k ≥ 2. We prove that for acyclic digraphs the existence of an out‐branching satisfying prescribed bounds on the out‐degrees of each vertex can be checked in polynomial time. A corollary of this is that the existence of arc‐disjoint branchings , , where the first is an out‐branching rooted at s and the second an in‐branching rooted at t, can be checked in polynomial time for the class of acyclic digraphs © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 297–307, 2003     

A generalization of the Oberwolfach problem

Let n > 1 be an integer and let a₂,a₃,…,a_n be nonnegative integers such that . Then can be factored into ‐factors, ‐factors,…, ‐factors, plus a 1‐factor. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 151–161, 2002     

A Closure for 1‐Hamilton‐Connectedness in Claw‐Free Graphs

A graph G is 1‐Hamilton‐connected if is Hamilton‐connected for every vertex . In the article, we introduce a closure concept for 1‐Hamilton‐connectedness in claw‐free graphs. If is a (new) closure of a claw‐free graph G, then is 1‐Hamilton‐connected if and only if G is 1‐Hamilton‐connected, is the line graph of a multigraph, and for some , is the line graph of a multigraph with at most two triangles or at most one double edge. As applications, we prove that Thomassen's Conjecture (every 4‐connected line graph is hamiltonian) is equivalent to the statement that every 4‐connected claw‐free graph is 1‐Hamilton‐connected, and we present results showing that every 5‐connected claw‐free graph with minimum degree at least 6 is 1‐Hamilton‐connected and that every 4‐connected claw‐free and hourglass‐free graph is 1‐Hamilton‐connected.     

Circuits through prescribed vertices in k‐connected k‐regular graphs

We show that every set of vertices in a k‐connected k‐regular graph belongs to some circuit. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 145–163, 2002     

A list analogue of equitable coloring

Given lists of available colors assigned to the vertices of a graph G, a list coloring is a proper coloring of G such that the color on each vertex is chosen from its list. If the lists all have size k, then a list coloring is equitable if each color appears on at most vertices. A graph is equitably k-choosable if such a coloring exists whenever the lists all have size k. We prove that G is equitably k-choosable when unless G contains or k is odd and . For forests, the threshold improves to . If G is a 2-degenerate graph (given k ≥ 5) or a connected interval graph (other than ), then G is equitably k-choosable when . © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 166–177, 2003     

Explicit sparse almost‐universal graphs for ${\bf {{\cal G}(n, {k \over n})}}$

For any integer n, let be a probability distribution on the family of graphs on n vertices (where every such graph has nonzero probability associated with it). A graph Γ is ‐almost‐universal if Γ satisifies the following: If G is chosen according to the probability distribution , then G is isomorphic to a subgraph of Γ with probability 1 ‐ . For any p ∈ [0,1], let (n,p) denote the probability distribution on the family of graphs on n vertices, where two vertices u and v form an edge with probability p, and the events {u and v form an edge}; u,v ∈ V (G) are mutually independent. For k ≥ 4 and n sufficiently large we construct a ‐almost‐universal‐graph on n vertices and with O(n)polylog(n) edges, where q = ? ? for such k ≤ 6, and where q = ? ? for k ≥ 7. The number of edges is close to the lower bound of Ω( ) for the number of edges in a universal graph for the family of graphs with n vertices and maximum degree k. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Graph classes characterized both by forbidden subgraphs and degree sequences

Given a set of graphs, a graph G is ‐free if G does not contain any member of as an induced subgraph. We say that is a degree‐sequence‐forcing set if, for each graph G in the class of ‐free graphs, every realization of the degree sequence of G is also in . We give a complete characterization of the degree‐sequence‐forcing sets when has cardinality at most two. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 131–148, 2008     

Critical graphs for subpancyclicity of 3‐connected claw‐free graphs

Let be the family of graphs G such that all sufficiently large k ‐connected claw‐free graphs which contain no induced copies of G are subpancyclic. We show that for every k≥3 the family is infinite and make the first step toward the complete characterization of the family . © 2009 Wiley Periodicals, Inc. J Graph Theory 62, 263–278, 2009     

Families of pairs of graphs with a large number of common cards

The vertex‐deleted subgraph G?v, obtained from the graph G by deleting the vertex v and all edges incident to v, is called a card of G. The deck of G is the multiset of its unlabelled vertex‐deleted subgraphs. The number of common cards of G and H (or between G and H) is the cardinality of the multiset intersection of the decks of G and H. In this article, we present infinite families of pairs of graphs of order n ≥ 4 that have at least \begin{eqnarray*}2\lfloor\frac{1}{3}(n-1)\rfloor\end{eqnarray*} common cards; we conjecture that these, along with a small number of other families constructed from them, are the only pairs of graphs having this many common cards, for sufficiently large n. This leads us to propose a new stronger version of the Reconstruction Conjecture. In addition, we present an infinite family of pairs of graphs with the same degree sequence that have \begin{eqnarray*}\frac{2}{3}(n+5-2\sqrt{3n+6})\end{eqnarray*} common cards, for appropriate values of n, from which we can construct pairs having slightly fewer common cards for all other values of n≥10. We also present infinite families of pairs of forests and pairs of trees with \begin{eqnarray*}2\lfloor\frac{1}{3}(n-4)\rfloor\end{eqnarray*} and \begin{eqnarray*}2\lfloor\frac{1}{3}(n-5)\rfloor\end{eqnarray*} common cards, respectively. We then present new families that have the maximum number of common cards when one graph is connected and the other disconnected. Finally, we present a family with a large number of common cards, where one graph is a tree and the other unicyclic, and discuss how many cards are required to determine whether a graph is a tree. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 146–163, 2010     

Overfull conjecture for graphs with high minimum degree

Chetwynd and Hilton showed that any regular graph G of even order n which has relatively high degree has a 1‐factorization. This is equivalent to saying that under these conditions G has chromatic index equal to its maximum degree . Using this result, we show that any (not necessarily regular) graph G of even order n that has sufficiently high minimum degree has chromatic index equal to its maximum degree providing that G does not contain an “overfull” subgraph, that is, a subgraph which trivially forces the chromatic index to be more than the maximum degree. This result thus verifies the Overfull Conjecture for graphs of even order and sufficiently high minimum degree. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 73–80, 2004     

On graphs with subgraphs having large independence numbers

Let G be a graph on n vertices in which every induced subgraph on vertices has an independent set of size at least . What is the largest so that every such G must contain an independent set of size at least q? This is one of the several related questions raised by Erd?s and Hajnal. We show that , investigate the more general problem obtained by changing the parameters s and t, and discuss the connection to a related Ramsey‐type problem. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 149–157, 2007     

Total relative displacement of vertex permutations of K

Let α denote a permutation of the n vertices of a connected graph G. Define δ_α(G) to be the number , where the sum is over all the unordered pairs of distinct vertices of G. The number δ_α(G) is called the total relative displacement of α (in G). So, permutation α is an automorphism of G if and only if δ_α(G) = 0. Let π(G) denote the smallest positive value of δ_α(G) among the n! permutations α of the vertices of G. A permutation α for which π(G) = δ_α(G) has been called a near‐automorphism of G [ 2 ]. We determine π(K) and describe permutations α of K for which π(K) = δ_α(K). This is done by transforming the problem into the combinatorial optimization problem of maximizing the sums of the squares of the entries in certain t by t matrices with non–negative integer entries in which the sum of the entries in the ith row and the sum of the entries in the ith column each equal to n_i,1≤i≤t. We prove that for positive integers, n₁≤n₂≤…≤n_t, where t≥2 and n_t≥2, where k₀ is the smallest index for which n = n+1. As a special case, we correct the value of π(K_m,n), for all m and n at least 2, given by Chartrand, Gavlas, and VanderJagt [ 2 ]. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 85–100, 2002     

More results on perfect (3,3,6k + 4; 6k − 2)‐threshold schemes

A (2,3)‐packing on X is a pair (X, ), where is a set of 3‐subsets (called blocks) of X, such that any pair of distinct points from X occurs together in at most one block. Its leave is a graph (X,E) such that E consists of all the pairs which do not appear in any block of . In this article, we shall construct a set of 6k ? 2 disjoint (2,3)‐packings of order 6k + 4 with K_1,3 ∪ 3kK₂ or G₁ ∪ (3k ? 1)K₂ as their common leave for any integer k ≥ 1 with a few possible exceptions (G₁ is a special graph of order 6). Such a system can be used to construct perfect threshold schemes as noted by Schellenberg and Stinson ( 22 ). © 2006 Wiley Periodicals, Inc. J Combin Designs     

The phase transition in random graphs: A simple proof

The classical result of Erd?s and Rényi asserts that the random graph G(n,p) experiences sharp phase transition around \begin{align*}p=\frac{1}{n}\end{align*} – for any ε > 0 and \begin{align*}p=\frac{1-\epsilon}{n}\end{align*}, all connected components of G(n,p) are typically of size O_ε(log n), while for \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, with high probability there exists a connected component of size linear in n. We provide a very simple proof of this fundamental result; in fact, we prove that in the supercritical regime \begin{align*}p=\frac{1+\epsilon}{n}\end{align*}, the random graph G(n,p) contains typically a path of linear length. We also discuss applications of our technique to other random graph models and to positional games. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Tauberian theorem for m‐spherical transforms on the Heisenberg group

In this paper we prove a Tauberian type theorem for the space L ( H _n ). This theorem gives sufficient conditions for a L ( H _n ) submodule J ? L ( H _n ) to make up all of L ( H _n ). As a consequence of this theorem, we are able to improve previous results on the Pompeiu problem with moments on the Heisenberg group for the space L^∞( H _n ). In connection with the Pompeiu problem, given the vanishing of integrals ∫ z ^m L _g f ( z , 0) dσ ( z ) = 0 for all g ∈ H _n and i = 1, 2 for appropriate radii r₁ and r₂, we now have the (improved) conclusion f ≡ 0, where = · · · and form the standard basis for T^(0,1)( H _n ). (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)