On Meyniel's conjecture of the cop number

Meyniel conjectured that the cop number c(G) of any connected graph G on n vertices is at most for some constant C. In this article, we prove Meyniel's conjecture in special cases that G has diameter 2 or G is a bipartite graph of diameter 3. For general connected graphs, we prove , improving the best previously known upper‐bound O(n/ lnn) due to Chiniforooshan.     

Maximal Induced Matchings in Triangle‐Free Graphs

An induced matching in a graph is a set of edges whose endpoints induce a 1‐regular subgraph. It is known that every n‐vertex graph has at most  maximal induced matchings, and this bound is the best possible. We prove that every n‐vertex triangle‐free graph has at most  maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K_{3, 3}. Our result implies that all maximal induced matchings in an n‐vertex triangle‐free graph can be listed in time , yielding the fastest known algorithm for finding a maximum induced matching in a triangle‐free graph.     

Improved bounds for minimal feedback vertex sets in tournaments

We study feedback vertex sets (FVS) in tournaments, which are orientations of complete graphs. As our main result, we show that any tournament on n nodes has at most 1.5949ⁿ minimal FVS. This significantly improves the previously best upper bound of 1.6667ⁿ by Fomin et al. [STOC 2016] and 1.6740ⁿ by Gaspers and Mnich [J. Graph Theory 72 (1):72–89, 2013]. Our new upper bound almost matches the best‐known lower bound of , due to Gaspers and Mnich. Our proof is algorithmic, and shows that all minimal FVS of tournaments can be enumerated in time .     

Total Domination in Graphs with Diameter 2

The total domination number of a graph G is the minimum cardinality of a set S of vertices, so that every vertex of G is adjacent to a vertex in S. In this article, we determine an optimal upper bound on the total domination number of a graph with diameter 2. We show that for every graph G on n vertices with diameter 2, . This bound is optimal in the sense that given any , there exist graphs G with diameter 2 of all sufficiently large even orders n such that .     

Graph operations and upper bounds on graph homomorphism counts

We construct a family of countexamples to a conjecture of Galvin [5], which stated that for any n‐vertex, d‐regular graph G and any graph H (possibly with loops), where is the number of homomorphisms from G to H. By exploiting properties of the graph tensor product and graph exponentiation, we also find new infinite families of H for which the bound stated above on holds for all n‐vertex, d‐regular G. In particular, we show that if H_WR is the complete looped path on three vertices, also known as the Widom–Rowlinson graph, then for all n‐vertex, d‐regular G. This verifies a conjecture of Galvin.     

On the number of minimal separators in graphs

Weconsider the largest number of minimal separators a graph on n vertices can have.

• – We give a new proof that this number is in .
• – We prove that this number is in , improving on the previous best lower bound of .

This gives also an improved lower bound on the number of potential maximal cliques in a graph. We would like to emphasize that our proofs are short, simple, and elementary.     

Pebbling Graphs of Diameter Three and Four

Given a configuration of pebbles on the vertices of a connected graph G, a pebbling move is defined as the removal of two pebbles from some vertex and the placement of one of these on an adjacent vertex. The pebbling number of a graph G is the smallest integer k such that for each vertex v and each configuration of k pebbles on G there is a sequence of pebbling moves that places at least one pebble on v. We improve on a bound of Bukh by showing that the pebbling number of a graph of diameter three on n vertices is at most , and this bound is best possible. Further, we obtain an asymptotic bound of for the pebbling number of graphs of diameter four. Finally, we prove an asymptotic bound for pebbling graphs of arbitrary diameter, namely that the pebbling number for a diameter d graph on n vertices is at most , where is a constant depending upon d. This also improves another bound of Bukh.     

Pancyclic subgraphs of random graphs

An n‐vertex graph is called pancyclic if it contains a cycle of length t for all 3≤t≤n. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if p>n^?1/2, then the random graph G(n, p) a.a.s. satisfies the following property: Every Hamiltonian subgraph of G(n, p) with more than edges is pancyclic. This result is best possible in two ways. First, the range of p is asymptotically tight; second, the proportion of edges cannot be reduced. Our theorem extends a classical theorem of Bondy, and is closely related to a recent work of Krivelevich et al. The proof uses a recent result of Schacht (also independently obtained by Conlon and Gowers). © 2011 Wiley Periodicals, Inc.     

Average Distance,Independence Number,and Spanning Trees

Let G be a connected graph of order n and independence number α. We prove that G has a spanning tree with average distance at most , if , and at most , if . As a corollary, we obtain, for n sufficiently large, an asymptotically sharp upper bound on the average distance of G in terms of its independence number. This bound, apart from confirming and improving on a conjecture of Graffiti [8], is a strengthening of a theorem of Chung [1], and that of Fajtlowicz and Waller [8], on average distance and independence number of a graph.     

SEFE without Mapping via Large Induced Outerplane Graphs in Plane Graphs

We show that every n‐vertex planar graph admits a simultaneous embedding without mapping and with fixed edges with any ‐vertex planar graph. In order to achieve this result, we prove that every n‐vertex plane graph has an induced outerplane subgraph containing at least vertices. Also, we show that every n‐vertex planar graph and every n‐vertex planar partial 3‐tree admit a simultaneous embedding without mapping and with fixed edges.     

Constructing a Family of 4‐Critical Planar Graphs with High Edge Density

A graph is a k‐critical graph if G is not ‐colorable but every proper subgraph of G is ‐colorable. In this article, we construct a family of 4‐critical planar graphs with n vertices and edges. As a consequence, this improves the bound for the maximum edge density attained by Abbott and Zhou. We conjecture that this is the largest edge density for a 4‐critical planar graph.     

Chordal 2‐Connected Graphs and Spanning Trees

We present a transformation on a chordal 2‐connected simple graph that decreases the number of spanning trees. Based on this transformation, we show that for positive integers n, m with , the threshold graph having n vertices and m edges that consists of an ‐clique and vertices of degree 2 is the only graph with the fewest spanning trees among all 2‐connected chordal graphs on n vertices and m edges.     

Diameter of random spanning trees in a given graph

Motivated by the observation that the sparse tree‐like subgraphs in a small world graph have large diameter, we analyze random spanning trees in a given host graph. We show that the diameter of a random spanning tree of a given host graph G is between and with high probability., where c and c′ depend on the spectral gap of G and the ratio of the moments of the degree sequence. For the special case of regular graphs, this result improves the previous lower bound by Aldous by a factor of logn. Copyright © 2011 John Wiley Periodicals, Inc. J Graph Theory 69: 223–240, 2012     

Identifying Codes in Line Graphs

An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbors within the code. We study the edge‐identifying code problem, i.e. the identifying code problem in line graphs. If denotes the size of a minimum identifying code of an identifiable graph G, we show that the usual bound , where n denotes the order of G, can be improved to in the class of line graphs. Moreover, this bound is tight. We also prove that the upper bound , where is the line graph of G, holds (with two exceptions). This implies that a conjecture of R. Klasing, A. Kosowski, A. Raspaud, and the first author holds for a subclass of line graphs. Finally, we show that the edge‐identifying code problem is NP‐complete, even for the class of planar bipartite graphs of maximum degree 3 and arbitrarily large girth.     

Degree sum and vertex dominating paths

A vertex dominating path in a graph is a path P such that every vertex outside P has a neighbor on P. In 1988 H. Broersma [5] stated a result implying that every n‐vertex k‐connected graph G such that contains a vertex dominating path. We provide a short, self‐contained proof of this result and further show that every n‐vertex k‐connected graph such that contains a vertex dominating path of length at most , where T is a minimum dominating set of vertices. An immediate corollary of this result is that every such graph contains a vertex dominating path with length bounded above by a logarithmic function of the order of the graph. To derive this result, we prove that every n‐vertex k‐connected graph with contains a path of length at most , through any set of T vertices where .     

Packing of graphic n‐tuples

An n‐tuple π (not necessarily monotone) is graphic if there is a simple graph G with vertex set {v₁, …, v_n} in which the degree of v_i is the ith entry of π. Graphic n‐tuples (d, …, d) and (d, …, d) pack if there are edge‐disjoint n‐vertex graphs G₁ and G₂ such that d(v_i) = d and d(v_i) = d for all i. We prove that graphic n‐tuples π₁ and π₂ pack if , where Δand δdenote the largest and smallest entries in π₁ + π₂ (strict inequality when δ = 1); also, the bound is sharp. Kundu and Lovász independently proved that a graphic n‐tuple π is realized by a graph with a k‐factor if the n‐tuple obtained by subtracting k from each entry of π is graphic; for even n we conjecture that in fact some realization has k edge‐disjoint 1‐factors. We prove the conjecture in the case where the largest entry of π is at most n/2 + 1 and also when k?3. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Hadwiger's Conjecture for the Complements of Kneser Graphs

Hadwiger's conjecture asserts that every graph with chromatic number t contains a complete minor of order t. Given integers , the Kneser graph is the graph with vertices the k‐subsets of an n‐set such that two vertices are adjacent if and only if the corresponding k‐subsets are disjoint. We prove that Hadwiger's conjecture is true for the complements of Kneser graphs.     

Moore Graphs and Cycles Are Extremal Graphs for Convex Cycles

Let denote the number of convex cycles of a simple graph G of order n, size m, and girth . It is proved that and that equality holds if and only if G is an even cycle or a Moore graph. The equality also holds for a possible Moore graph of diameter 2 and degree 57 thus giving a new characterization of Moore graphs.     

A Sufficient Condition for Edge Chromatic Critical Graphs to Be Hamiltonian—An Approach to Vizing's 2‐Factor Conjecture

In this article, we consider Vizing's 2‐Factor Conjecture which claims that any Δ‐critical graph has a 2‐factor, and show that if G is a Δ‐critical graph with n vertices satisfying , then G is Hamiltonian and thus G has a 2‐factor. Meanwhile in this article, we also consider long cycles of overfull critical graphs and obtain that if G is an overfull Δ‐critical graph with n vertices, then the circumference of G is at least min.© 2012 Wiley Periodicals, Inc. J. Graph Theory 00: 1‐14, 2012     

Degree Conditions for Matchability in 3‐Partite Hypergraphs

We study conjectures relating degree conditions in 3‐partite hypergraphs to the matching number of the hypergraph, and use topological methods to prove special cases. In particular, we prove a strong version of a theorem of Drisko [14] (as generalized by the first two authors [2]), that every family of $2n-1$ matchings of size n in a bipartite graph has a partial rainbow matching of size n. We show that milder restrictions on the sizes of the matchings suffice. Another result that is strengthened is a theorem of Cameron and Wanless [11], that every $n\times n$ Latin square has a generalized diagonal (set of n entries, each in a different row and column) in which no symbol appears more than twice. We show that the same is true under the weaker condition that the square is row‐Latin.