Extremal Graphs With a Given Number of Perfect Matchings

Let denote the maximum number of edges in a graph having n vertices and exactly p perfect matchings. For fixed p, Dudek and Schmitt showed that for some constant when n is at least some constant . For , they also determined and . For fixed p, we show that the extremal graphs for all n are determined by those with vertices. As a corollary, a computer search determines and for . We also present lower bounds on proving that for (as conjectured by Dudek and Schmitt), and we conjecture an upper bound on . Our structural results are based on Lovász's Cathedral Theorem.     

Circular Chromatic Indices of Regular Graphs

The circular chromatic index of a graph G, written , is the minimum r permitting a function such that whenever e and are adjacent. It is known that for any , there is a 3‐regular simple graph G with . This article proves the following results: Assume is an odd integer. For any , there is an n‐regular simple graph G with . For any , there is an n‐regular multigraph G with .     

Smallest domination number and largest independence number of graphs and forests with given degree sequence

For a sequence d of nonnegative integers, let and be the sets of all graphs and forests with degree sequence d, respectively. Let , , , and where is the domination number and is the independence number of a graph G. Adapting results of Havel and Hakimi, Rao showed in 1979 that can be determined in polynomial time. We establish the existence of realizations with , and with and that have strong structural properties. This leads to an efficient algorithm to determine for every given degree sequence d with bounded entries as well as closed formulas for and .     

List‐Coloring the Squares of Planar Graphs without 4‐Cycles and 5‐Cycles

Let G be a planar graph without 4‐cycles and 5‐cycles and with maximum degree . We prove that . For arbitrarily large maximum degree Δ, there exist planar graphs of girth 6 with . Thus, our bound is within 1 of being optimal. Further, our bound comes from coloring greedily in a good order, so the bound immediately extends to online list‐coloring. In addition, we prove bounds for ‐labeling. Specifically, and, more generally, , for positive integers p and q with . Again, these bounds come from a greedy coloring, so they immediately extend to the list‐coloring and online list‐coloring variants of this problem.     

An Asymptotic Version of the Multigraph 1‐Factorization Conjecture

We give a self‐contained proof that for all positive integers r and all , there is an integer such that for all any regular multigraph of order 2n with multiplicity at most r and degree at least is 1‐factorizable. This generalizes results of Perkovi? and Reed (Discrete Math 165/166 (1997), 567–578) and Plantholt and Tipnis (J London Math Soc 44 (1991), 393–400).     

Regular Hypertournaments and Arc‐Pancyclicity

A k‐hypertournament H on n vertices () is a pair , where V is the vertex set of H and A is a set of k‐tuples of vertices, called arcs, such that for all subsets with , A contains exactly one permutation of S as an arc. Recently, Li et al. showed that any strong k‐hypertournament H on n vertices, where , is vertex‐pancyclic, an extension of Moon's theorem for tournaments. In this article, we examine several generalizations of regular tournaments and prove the following generalization of Alspach's theorem concerning arc‐pancyclicity: Every Σ‐regular k‐hypertournament on n vertices, where , is arc‐pancyclic.     

Chasing a Fast Robber on Planar Graphs and Random Graphs

We consider a variant of the Cops and Robber game, in which the robber has unbounded speed, that is, can take any path from her vertex in her turn, but she is not allowed to pass through a vertex occupied by a cop. Let denote the number of cops needed to capture the robber in a graph G in this variant, and let denote the treewidth of G. We show that if G is planar then , and there is a polynomial‐time constant‐factor approximation algorithm for computing . We also determine, up to constant factors, the value of of the Erd?s–Rényi random graph for all admissible values of p, and show that when the average degree is ω(1), is typically asymptotic to the domination number.     

Full subgraphs

Let be a graph of density p on n vertices. Following Erdős, Łuczak, and Spencer, an m‐vertex subgraph H of G is called full if H has minimum degree at least . Let denote the order of a largest full subgraph of G. If is a nonnegative integer, define Erdős, Łuczak, and Spencer proved that for , In this article, we prove the following lower bound: for , Furthermore, we show that this is tight up to a multiplicative constant factor for infinitely many p near the elements of . In contrast, we show that for any n‐vertex graph G, either G or contains a full subgraph on vertices. Finally, we discuss full subgraphs of random and pseudo‐random graphs, and several open problems.     

Non‐Critical Vertices and Long Circuits in Strong Tournaments of Order n and Diameter d

Let T be a strong tournament of order with diameter . A vertex w in T is non‐critical if the subtournament is also strong. In the opposite case, it is a critical vertex. In the present article, we show that T has at most critical vertices. This fact and Moon's vertex‐pancyclic theorem imply that for , it contains at least circuits of length . We describe the class of all strong tournaments of order with diameter for which this lower bound is achieved and show that for , the minimum number of circuits of length in a tournament of this class is equal to . In turn, the minimum among all strong tournaments of order with diameter 2 grows exponentially with respect to n for any given . Finally, for , we select a strong tournament of order n with diameter d and conjecture that for any strong tournament T of order n whose diameter does not exceed d, the number of circuits of length ? in T is not less than that in for each possible ?. Moreover, if these two numbers are equal to each other for some given , where , then T is isomorphic to either or its converse . For , this conjecture was proved by Las Vergnas. In the present article, we confirm it for the case . In an Appendix, some problems concerning non‐critical vertices are considered for generalizations of tournaments.     

On Generalized Ramsey Numbers for 3‐Uniform Hypergraphs

The well‐known Ramsey number is the smallest integer n such that every ‐free graph of order n contains an independent set of size u. In other words, it contains a subset of u vertices with no K₂. Erd?s and Rogers introduced a more general problem replacing K₂ by  for . Extending the problem of determining Ramsey numbers they defined the numbers where the minimum is taken over all ‐free graphs G of order n. In this note, we study an analogous function for 3‐uniform hypergraphs. In particular, we show that there are constants c₁ and c₂ depending only on s such that      

Cycles Avoiding a Color in Colorful Graphs

The Ramsey numbers of cycles imply that every 2‐edge‐colored complete graph on n vertices contains monochromatic cycles of all lengths between 4 and at least . We generalize this result to colors by showing that every k‐edge‐colored complete graph on vertices contains ‐edge‐colored cycles of all lengths between 3 and at least .     

Edge‐transitive homogeneous factorizations of complete uniform hypergraphs

For a finite set V and a positive integer k with , letting be the set of all k‐subsets of V, the pair is called the complete k‐hypergraph on V, while each k‐subset of V is called an edge. A factorization of the complete k‐hypergraph of index , simply a ‐factorization of order n, is a partition of the edges into s disjoint subsets such that each k‐hypergraph , called a factor, is a spanning subhypergraph of . Such a factorization is homogeneous if there exist two transitive subgroups G and M of the symmetric group of degree n such that G induces a transitive action on the set and M lies in the kernel of this action. In this article, we give a classification of homogeneous factorizations of that admit a group acting transitively on the edges of . It is shown that, for and , there exists an edge‐transitive homogeneous ‐factorization of order n if and only if is one of (32, 3, 5), (32, 3, 31), (33, 4, 5), , and , where and q is a prime power with .     

Dominating sets inducing large components in maximal outerplanar graphs

For a maximal outerplanar graph G of order n at least three, Matheson and Tarjan showed that G has domination number at most . Similarly, for a maximal outerplanar graph G of order n at least five, Dorfling, Hattingh, and Jonck showed, by a completely different approach, that G has total domination number at most unless G is isomorphic to one of two exceptional graphs of order 12. We present a unified proof of a common generalization of these two results. For every positive integer k, we specify a set of graphs of order at least and at most such that every maximal outerplanar graph G of order n at least that does not belong to has a dominating set D of order at most such that every component of the subgraph of G induced by D has order at least k.     

Saturation Numbers in Tripartite Graphs

Given graphs H and F, a subgraph is an F‐saturated subgraph of H if , but for all . The saturation number of F in H, denoted , is the minimum number of edges in an F‐saturated subgraph of H. In this article, we study saturation numbers of tripartite graphs in tripartite graphs. For and n₁, n₂, and n₃ sufficiently large, we determine and exactly and within an additive constant. We also include general constructions of ‐saturated subgraphs of with few edges for .     

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 .     

More on the Bipartite Decomposition of Random Graphs

For a graph , let denote the minimum number of pairwise edge disjoint complete bipartite subgraphs of G so that each edge of G belongs to exactly one of them. It is easy to see that for every graph G , , where is the maximum size of an independent set of G . Erd?s conjectured in the 80s that for almost every graph G equality holds, that is that for the random graph , with high probability, that is with probability that tends to 1 as n tends to infinity. The first author showed that this is slightly false, proving that for most values of n tending to infinity and for , with high probability. We prove a stronger bound: there exists an absolute constant so that with high probability.     

Edge‐Disjoint Spanning Trees,Edge Connectivity,and Eigenvalues in Graphs

Let and denote the second largest eigenvalue and the maximum number of edge‐disjoint spanning trees of a graph G, respectively. Motivated by a question of Seymour on the relationship between eigenvalues of a graph G and bounds of , Cioab? and Wong conjectured that for any integers and a d‐regular graph G, if , then . They proved the conjecture for , and presented evidence for the cases when . Thus the conjecture remains open for . We propose a more general conjecture that for a graph G with minimum degree , if , then . In this article, we prove that for a graph G with minimum degree δ, each of the following holds.

• (i) For , if and , then .
• (ii) For , if and , then .

Our results sharpen theorems of Cioab? and Wong and give a partial solution to Cioab? and Wong's conjecture and Seymour's problem. We also prove that for a graph G with minimum degree , if , then the edge connectivity is at least k, which generalizes a former result of Cioab?. As corollaries, we investigate the Laplacian and signless Laplacian eigenvalue conditions on and edge connectivity.     

Tiling 3‐Uniform Hypergraphs With

Let denote the hypergraph consisting of two triples on four points. For an integer n, let denote the smallest integer d so that every 3‐uniform hypergraph G of order n with minimum pair‐degree contains vertex‐disjoint copies of . Kühn and Osthus (J Combin Theory, Ser B 96(6) (2006), 767–821) proved that holds for large integers n. Here, we prove the exact counterpart, that for all sufficiently large integers n divisible by 4, A main ingredient in our proof is the recent “absorption technique” of Rödl, Ruciński, and Szemerédi (J. Combin. Theory Ser. A 116(3) (2009), 613–636).     

The Maximum Number of Complete Subgraphs of Fixed Size in a Graph with Given Maximum Degree

In this article, we make progress on a question related to one of Galvin that has attracted substantial attention recently. The question is that of determining among all graphs G with n vertices and , which has the most complete subgraphs of size t, for . The conjectured extremal graph is , where with . Gan et al. (Combin Probab Comput 24(3) (2015), 521–527) proved the conjecture when , and also reduced the general conjecture to the case . We prove the conjecture for and also establish a weaker form of the conjecture for all r.     

Packing Triangles in Regular Tournaments

We prove that a regular tournament with n vertices has more than pairwise arc‐disjoint directed triangles. On the other hand, we construct regular tournaments with a feedback arc set of size less than , so these tournaments do not have pairwise arc‐disjoint triangles.