Given a digraph *G*, we propose a new method to find the recurrence equation for the number of vertices of the *k*-iterated line digraph , for , where . We obtain this result by using the minimal polynomial of a quotient digraph of *G*.

We consider random-turn positional games, introduced by Peres, Schramm, Sheffield, and Wilson in 2007. A *p*-random-turn positional game is a two-player game, played the same as an ordinary positional game, except that instead of alternating turns, a coin is being tossed before each turn to decide the identity of the next player to move (the probability of Player I to move is *p*). We analyze the random-turn version of several classical Maker–Breaker games such as the game Box (introduced by Chvátal and Erdős in 1987), the Hamilton cycle game and the *k*-vertex-connectivity game (both played on the edge set of ). For each of these games we provide each of the players with a (randomized) efficient strategy that typically ensures his win in the asymptotic order of the minimum value of *p* for which he typically wins the game, assuming optimal strategies of both players.

A graph with a trivial automorphism group is said to be *rigid*. Wright proved (Acta Math 126(1) (1971), 1–9) that for a random graph is rigid whp (with high probability). It is not hard to see that this lower bound is sharp and for with positive probability is nontrivial. We show that in the sparser case , it holds whp that *G*'s 2-core is rigid. We conclude that for all *p*, a graph in is reconstructible whp. In addition this yields for a canonical labeling algorithm that almost surely runs in polynomial time with *o*(1) error rate. This extends the range for which such an algorithm is currently known (T. Czajka and G. Pandurangan, J Discrete Algorithms 6(1) (2008), 85–92).

We look at several saturation problems in complete balanced blow-ups of graphs. We let denote the blow-up of *H* onto parts of size *n* and refer to a copy of *H* in as *partite* if it has one vertex in each part of . We then ask how few edges a subgraph *G* of can have such that *G* has no partite copy of *H* but such that the addition of any new edge from creates a partite *H*. When *H* is a triangle this value was determined by Ferrara, Jacobson, Pfender, and Wenger in . Our main result is to calculate this value for when *n* is large. We also give exact results for paths and stars and show that for 2-connected graphs the answer is linear in *n* whilst for graphs that are not 2-connected the answer is quadratic in *n*. We also investigate a similar problem where *G* is permitted to contain partite copies of *H* but we require that the addition of any new edge from creates an extra partite copy of *H*. This problem turns out to be much simpler and we attain exact answers for all cliques and trees.

A graph *G* is called -choosable if for any list assignment *L* that assigns to each vertex *v* a set of *a* permissible colors, there is a *b*-tuple *L*-coloring of *G*. An (*a*, 1)-choosable graph is also called *a*-choosable. In the pioneering article on list coloring of graphs by Erdős et al. , 2-choosable graphs are characterized. Confirming a special case of a conjecture in , Tuza and Voigt proved that 2-choosable graphs are -choosable for any positive integer *m*. On the other hand, Voigt proved that if *m* is an odd integer, then these are the only -choosable graphs; however, when *m* is even, there are -choosable graphs that are not 2-choosable. A graph is called 3-choosable-critical if it is not 2-choosable, but all its proper subgraphs are 2-choosable. Voigt conjectured that for every positive integer *m*, all bipartite 3-choosable-critical graphs are -choosable. In this article, we determine which 3-choosable-critical graphs are (4, 2)-choosable, refuting Voigt's conjecture in the process. Nevertheless, a weaker version of the conjecture is true: we prove that there is an even integer *k* such that for any positive integer *m*, every bipartite 3-choosable-critical graph is -choosable. Moving beyond 3-choosable-critical graphs, we present an infinite family of non-3-choosable-critical graphs that have been shown by computer analysis to be (4, 2)-choosable. This shows that the family of all (4, 2)-choosable graphs has rich structure.

Given two graphs *G* and *H*, an *H*-*decomposition* of *G* is a partition of the edge set of *G* such that each part is either a single edge or forms a graph isomorphic to *H*. Let be the smallest number ϕ such that any graph *G* of order *n* admits an *H*-decomposition with at most ϕ parts. Pikhurko and Sousa conjectured that for and all sufficiently large *n*, where denotes the maximum number of edges in a graph on *n* vertices not containing *H* as a subgraph. Their conjecture has been verified by Özkahya and Person for all edge-critical graphs *H*. In this article, the conjecture is verified for the *k*-fan graph. The *k*-*fan graph*, denoted by , is the graph on vertices consisting of *k* triangles that intersect in exactly one common vertex called the *center* of the *k*-fan.

For graphs *F* and *H*, we say *F* is *Ramsey for H* if every 2-coloring of the edges of *F* contains a monochromatic copy of *H*. The graph *F* is *Ramsey H*-*minimal* if *F* is Ramsey for *H* and there is no proper subgraph of *F* so that is Ramsey for *H*. Burr et al. defined to be the minimum degree of *F* over all Ramsey *H*-minimal graphs *F*. Define to be a graph on vertices consisting of a complete graph on *t* vertices and one additional vertex of degree *d*. We show that for all values ; it was previously known that , so it is surprising that is much smaller. We also make some further progress on some sparser graphs. Fox and Lin observed that for all graphs *H*, where is the minimum degree of *H*; Szabó et al. investigated which graphs have this property and conjectured that all bipartite graphs *H* without isolated vertices satisfy . Fox et al. further conjectured that all connected triangle-free graphs with at least two vertices satisfy this property. We show that *d*-regular 3-connected triangle-free graphs *H*, with one extra technical constraint, satisfy ; the extra constraint is that *H* has a vertex *v* so that if one removes *v* and its neighborhood from *H*, the remainder is connected.

We give a complete description of the set of triples of real numbers with the following property. There exists a constant *K* such that is a lower bound for the matching number of every connected subcubic graph *G*, where denotes the number of vertices of degree *i* for each *i*.

Given a directed graph, an acyclic set is a set of vertices inducing a directed subgraph with no directed cycle. In this note, we show that for all integers , there exist oriented planar graphs of order *n* and digirth *g* for which the size of the maximum acyclic set is at most . When this result disproves a conjecture of Harutyunyan and shows that a question of Albertson is best possible.

Tutte's 5-flow conjecture from 1954 states that every bridgeless graph has a nowhere-zero 5-flow. It suffices to prove the conjecture for cyclically 6-edge-connected cubic graphs. We prove that every cyclically 6-edge-connected cubic graph with oddness at most 4 has a nowhere-zero 5-flow. This implies that every minimum counterexample to the 5-flow conjecture has oddness at least 6.

In the *graph sharing game*, two players share a connected graph *G* with nonnegative weights assigned to the vertices claiming and collecting the vertices of *G* one by one, while keeping the set of all claimed vertices connected through the whole game. Each player wants to maximize the total weight of the vertices they have gathered by the end of the game, when the whole *G* has been claimed. It is proved that for any class of graphs with an odd number of vertices and with forbidden subdivision of a fixed graph (e.g., for the class of planar graphs with an odd number of vertices), there is a constant such that the first player can secure at least the proportion of the total weight of *G* whenever . Known examples show that such a constant does no longer exist if any of the two conditions on the class (an odd number of vertices or a forbidden subdivision) is removed. The main ingredient in the proof is a new structural result on weighted graphs with a forbidden subdivision.

Li et al. (Discrete Math 310 (2010), 3579–3583) asked how long the longest monochromatic cycle in a 2-edge-colored graph *G* with minimum degree at least could be. In this article, an answer is given for all to an asymptotic form of their question.

A spanning subgraph *F* of a graph *G* is called *perfect* if *F* is a forest, the degree of each vertex *x* in *F* is odd, and each tree of *F* is an induced subgraph of *G*. Alex Scott (Graphs Combin 17 (2001), 539–553) proved that every connected graph *G* contains a perfect forest if and only if *G* has an even number of vertices. We consider four generalizations to directed graphs of the concept of a perfect forest. While the problem of existence of the most straightforward one is NP-hard, for the three others this problem is polynomial-time solvable. Moreover, every digraph with only one strong component contains a directed forest of each of these three generalization types. One of our results extends Scott's theorem to digraphs in a nontrivial way.

The article gives a thorough introduction to spectra of digraphs via its Hermitian adjacency matrix. This matrix is indexed by the vertices of the digraph, and the entry corresponding to an arc from *x* to *y* is equal to the complex unity *i* (and its symmetric entry is ) if the reverse arc is not present. We also allow arcs in both directions and unoriented edges, in which case we use 1 as the entry. This allows to use the definition also for mixed graphs. This matrix has many nice properties; it has real eigenvalues and the interlacing theorem holds for a digraph and its induced subdigraphs. Besides covering the basic properties, we discuss many differences from the properties of eigenvalues of undirected graphs and develop basic theory. The main novel results include the following. Several surprising facts are discovered about the spectral radius; some consequences of the interlacing property are obtained; operations that preserve the spectrum are discussed—they give rise to a large number of cospectral digraphs; for every , all digraphs whose spectrum is contained in the interval are determined.

We study the class of 1-perfectly orientable graphs, that is, graphs having an orientation in which every out-neighborhood induces a tournament. 1-perfectly orientable graphs form a common generalization of chordal graphs and circular arc graphs. Even though they can be recognized in polynomial time, little is known about their structure. In this article, we develop several results on 1-perfectly orientable graphs. In particular, we (i) give a characterization of 1-perfectly orientable graphs in terms of edge clique covers, (ii) identify several graph transformations preserving the class of 1-perfectly orientable graphs, (iii) exhibit an infinite family of minimal forbidden induced minors for the class of 1-perfectly orientable graphs, and (iv) characterize the class of 1-perfectly orientable graphs within the classes of cographs and of cobipartite graphs. The class of 1-perfectly orientable cobipartite graphs coincides with the class of cobipartite circular arc graphs.

We present two heuristics for finding a small power dominating set of cubic graphs. We analyze the performance of these heuristics on random cubic graphs using differential equations. In this way, we prove that the proportion of vertices in a minimum power dominating set of a random cubic graph is asymptotically almost surely at most 0.067801. We also provide a corresponding lower bound of using known results on bisection width.

In this article, we introduce and study the properties of some target graphs for 2-edge-colored homomorphism. Using these properties, we obtain in particular that the 2-edge-colored chromatic number of the class of triangle-free planar graphs is at most 50. We also show that it is at least 12.

The partition of graphs into “nice” subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same-size stars, a problem known to be NP-complete even for the case of stars on three vertices. We perform a thorough computational complexity study of the problem on subclasses of perfect graphs and identify several polynomial-time solvable cases, for example, on interval graphs and bipartite permutation graphs, and also NP-complete cases, for example, on grid graphs and chordal graphs.

We prove that every normal plane map (NPM) has a path on three vertices (3-path) whose degree sequence is bounded from above by one of the following triplets: (3, 3, ∞), (3,15,3), (3,10,4), (3,8,5), (4,7,4), (5,5,7), (6,5,6), (3,4,11), (4,4,9), and (6,4,7). This description is tight in the sense that no its parameter can be improved and no term dropped. We also pose a problem of describing all tight descriptions of 3-paths in NPMs and make a modest contribution to it by showing that there exist precisely three one-term descriptions: (5, ∞, 6), (5, 10, ∞), and (10, 5, ∞).

Let *G* be a 5-connected triangulation of a surface Σ different from the sphere, and let be the Euler characteristic of Σ. Suppose that with even and *M* and *N* are two matchings in of sizes *m* and *n* respectively such that . It is shown that if the pairwise distance between any two elements of is at least five and the face-width of the embedding of *G* in Σ is at least , then there is a perfect matching *M*_{0} in containing *M* such that .

Given two graphs, a mapping between their edge-sets is *cycle-continuous*, if the preimage of every cycle is a cycle. The motivation for this definition is Jaeger's conjecture that for every bridgeless graph there is a cycle-continuous mapping to the Petersen graph, which, if solved positively, would imply several other important conjectures (e.g., the Cycle double cover conjecture). Answering a question of DeVos, Nešetřil, and Raspaud, we prove that there exists an infinite set of graphs with no cycle-continuous mapping between them. Further extending this result, we show that every countable poset can be represented by graphs and the existence of cycle-continuous mappings between them.

The complete graph on *n* vertices can be quadrangularly embedded on an orientable (resp. nonorientable) closed surface *F*^{2} with Euler characteristic if and only if (resp. and ). In this article, we shall show that if quadrangulates a closed surface *F*^{2}, then has a quadrangular embedding on *F*^{2} so that the length of each closed walk in the embedding has the parity specified by any given homomorphism , called the cycle parity.

The Erdős–Lovász Tihany conjecture asserts that every graph *G* with ) contains two vertex disjoint subgraphs *G*_{1} and *G*_{2} such that and . Under the same assumption on *G*, we show that there are two vertex disjoint subgraphs *G*_{1} and *G*_{2} of *G* such that (a) and or (b) and . Here, is the chromatic number of is the clique number of *G*, and col(*G*) is the coloring number of *G*.

For a graph *G*, let denote the largest *k* such that *G* has *k* pairwise disjoint pairwise adjacent connected nonempty subgraphs, and let denote the largest *k* such that *G* has *k* pairwise disjoint pairwise adjacent connected subgraphs of size 1 or 2. Hadwiger's conjecture states that , where is the chromatic number of *G*. Seymour conjectured for all graphs without antitriangles, that is, three pairwise nonadjacent vertices. Here we concentrate on graphs *G* with exactly one -coloring. We prove generalizations of the following statements: (i) if and *G* has exactly one -coloring then , where the proof does *not* use the four-color-theorem, and (ii) if *G* has no antitriangles and *G* has exactly one -coloring then .

Two Hamilton paths in are separated by a cycle of length *k* if their union contains such a cycle. For we bound the asymptotics of the maximum cardinality of a family of Hamilton paths in such that any pair of paths in the family is separated by a cycle of length *k*. We also deal with related problems, including directed Hamilton paths.

The choosability of a graph *G* is the minimum *k* such that having *k* colors available at each vertex guarantees a proper coloring. Given a toroidal graph *G*, it is known that , and if and only if *G* contains *K*_{7}. Cai et al. (J Graph Theory 65(1) (2010), 1–15) proved that a toroidal graph *G* without 7-cycles is 6-choosable, and if and only if *G* contains *K*_{6}. They also proved that a toroidal graph *G* without 6-cycles is 5-choosable, and conjectured that if and only if *G* contains *K*_{5}. We disprove this conjecture by constructing an infinite family of non-4-colorable toroidal graphs with neither *K*_{5} nor cycles of length at least 6; moreover, this family of graphs is embeddable on every surface except the plane and the projective plane. Instead, we prove the following slightly weaker statement suggested by Zhu: toroidal graphs containing neither (a *K*_{5} missing one edge) nor 6-cycles are 4-choosable. This is sharp in the sense that forbidding only one of the two structures does not ensure that the graph is 4-choosable.

For any graph *G*, let be the number of spanning trees of *G*, be the line graph of *G*, and for any nonnegative integer *r*, be the graph obtained from *G* by replacing each edge *e* by a path of length connecting the two ends of *e*. In this article, we obtain an expression for in terms of spanning trees of *G* by a combinatorial approach. This result generalizes some known results on the relation between and and gives an explicit expression if *G* is of order and size in which *s* vertices are of degree 1 and the others are of degree *k*. Thus we prove a conjecture on for such a graph *G*.

Given a graph *F*, a graph *G* is *uniquely F*-*saturated* if *F* is not a subgraph of *G* and adding any edge of the complement to *G* completes exactly one copy of *F*. In this article, we study uniquely -saturated graphs. We prove the following: (1) a graph is uniquely *C*_{5}-saturated if and only if it is a friendship graph. (2) There are no uniquely *C*_{6}-saturated graphs or uniquely *C*_{7}-saturated graphs. (3) For , there are only finitely many uniquely -saturated graphs (we conjecture that in fact there are none). Additionally, our results show that there are finitely many *k*-friendship graphs (as defined by Kotzig) for .

We prove that for every fixed *k*, the number of occurrences of the transitive tournament Tr_{k} of order *k* in a tournament on *n* vertices is asymptotically minimized when is random. In the opposite direction, we show that any sequence of tournaments achieving this minimum for any fixed is necessarily quasirandom. We present several other characterizations of quasirandom tournaments nicely complementing previously known results and relatively easily following from our proof techniques.

We construct for all a *k*-edge-connected digraph *D* with such that there are no edge-disjoint and paths. We use in our construction “self-similar” graphs which technique could be useful in other problems as well.

In this article we prove a new result about partitioning colored complete graphs and use it to determine certain Ramsey numbers exactly. The partitioning theorem we prove is that for , in every edge coloring of with the colors red and blue, it is possible to cover all the vertices with *k* disjoint red paths and a disjoint blue balanced complete -partite graph. When the coloring of is connected in red, we prove a stronger result—that it is possible to cover all the vertices with *k* red paths and a blue balanced complete -partite graph. Using these results we determine the Ramsey number of an *n*-vertex path, , versus a balanced complete *t*-partite graph on vertices, , whenever . We show that in this case , generalizing a result of Erdős who proved the case of this result. We also determine the Ramsey number of a path versus the power of a path . We show that , solving a conjecture of Allen, Brightwell, and Skokan.

A drawing of a graph is *pseudolinear* if there is a pseudoline arrangement such that each pseudoline contains exactly one edge of the drawing. The *pseudolinear crossing number* of a graph *G* is the minimum number of pairwise crossings of edges in a pseudolinear drawing of *G*. We establish several facts on the pseudolinear crossing number, including its computational complexity and its relationship to the usual crossing number and to the rectilinear crossing number. This investigation was motivated by open questions and issues raised by Marcus Schaefer in his comprehensive survey of the many variants of the crossing number of a graph.

A graph is called hypohamiltonian if it is not hamiltonian but becomes hamiltonian if any vertex is removed. Many hypohamiltonian planar cubic graphs have been found, starting with constructions of Thomassen in 1981. However, all the examples found until now had 4-cycles. In this note we present the first examples of hypohamiltonian planar cubic graphs with cyclic connectivity 5, and thus girth 5. We show by computer search that the smallest members of this class are three graphs with 76 vertices.

We study the existence and the number of *k*-dominating independent sets in certain graph families. While the case namely the case of maximal independent sets—which is originated from Erdős and Moser—is widely investigated, much less is known in general. In this paper we settle the question for trees and prove that the maximum number of *k*-dominating independent sets in *n*-vertex graphs is between and if , moreover the maximum number of 2-dominating independent sets in *n*-vertex graphs is between and . Graph constructions containing a large number of *k*-dominating independent sets are coming from product graphs, complete bipartite graphs, and finite geometries. The product graph construction is associated with the number of certain Maximum Distance Separable (MDS) codes.

A natural topic of algebraic graph theory is the study of vertex transitive graphs. In the present article, we investigate locally 3-transitive graphs of girth 4. Taking our former results on locally symmetric graphs of girth 4 as a starting point, we show what properties are retained if we weaken the requirement of local symmetry to local 3-transitivity.

Treewidth is a graph parameter of fundamental importance to algorithmic and structural graph theory. This article surveys several graph parameters tied to treewidth, including separation number, tangle number, well-linked number, and Cartesian tree product number. We review many results in the literature showing these parameters are tied to treewidth. In a number of cases we also improve known bounds, provide simpler proofs, and show that the inequalities presented are tight.

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*_{1}, *n*_{2}, and *n*_{3} sufficiently large, we determine and exactly and within an additive constant. We also include general constructions of -saturated subgraphs of with few edges for .

The class of cographs is known to have unbounded linear clique-width. We prove that a hereditary class of cographs has bounded linear clique-width if and only if it does not contain all quasi-threshold graphs or their complements. The proof borrows ideas from the enumeration of permutation classes.

The crossing number cr(*G*) of a graph *G* is the minimum number of crossings in a drawing of *G* in the plane with no more than two edges intersecting at any point that is not a vertex. The rectilinear crossing number of *G* is the minimum number of crossings in a such drawing of *G* with edges as straight line segments. Zarankiewicz proved in 1952 that . We generalize the upper bound to

and prove . We also show that for *n* large enough, and , with the tighter rectilinear lower bound established through the use of flag algebras. A complete multipartite graph is balanced if the partite sets all have the same cardinality. We study asymptotic behavior of the crossing number of the balanced complete *r*-partite graph. Richter and Thomassen proved in 1997 that the limit as of over the maximum number of crossings in a drawing of exists and is at most . We define and show that for a fixed *r* and the balanced complete *r*-partite graph, is an upper bound to the limit superior of the crossing number divided by the maximum number of crossings in a drawing.

*Equistable graphs* are graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight 1. *Strongly equistable graphs* are graphs such that for every and every nonempty subset *T* of vertices that is not a maximal stable set, there exist positive vertex weights assigning weight 1 to every maximal stable set such that the total weight of *T* does not equal *c*. *General partition graphs* are the intersection graphs of set systems over a finite ground set *U* such that every maximal stable set of the graph corresponds to a partition of *U*. General partition graphs are exactly the graphs every edge of which is contained in a strong clique. In 1994, Mahadev, Peled, and Sun proved that every strongly equistable graph is equistable, and conjectured that the converse holds as well. In 2009, Orlin proved that every general partition graph is equistable, and conjectured that the converse holds as well. Orlin's conjecture, if true, would imply the conjecture due to Mahadev, Peled, and Sun. An “intermediate” conjecture, posed by Miklavič and Milanič in 2011, states that every equistable graph has a strong clique. The above conjectures have been verified for several graph classes. We introduce the notion of equistarable graphs and based on it construct counterexamples to all three conjectures within the class of complements of line graphs of triangle-free graphs. We also show that not all strongly equistable graphs are general partition.

A graph is -colorable if its vertex set can be partitioned into *r* sets so that the maximum degree of the graph induced by is at most for each . For a given pair , the question of determining the minimum such that planar graphs with girth at least *g* are -colorable has attracted much interest. The finiteness of was known for all cases except when . Montassier and Ochem explicitly asked if *d*_{2}(5, 1) is finite. We answer this question in the affirmative with ; namely, we prove that all planar graphs with girth at least five are (1, 10)-colorable. Moreover, our proof extends to the statement that for any surface *S* of Euler genus γ, there exists a where graphs with girth at least five that are embeddable on *S* are (1, *K*)-colorable. On the other hand, there is no finite *k* where planar graphs (and thus embeddable on any surface) with girth at least five are (0, *k*)-colorable.

We show that a *k*-edge-connected graph on *n* vertices has at least spanning trees. This bound is tight if *k* is even and the extremal graph is the *n*-cycle with edge multiplicities . For *k* odd, however, there is a lower bound , where . Specifically, and . Not surprisingly, *c*_{3} is smaller than the corresponding number for 4-edge-connected graphs. Examples show that . However, we have no examples of 5-edge-connected graphs with fewer spanning trees than the *n*-cycle with all edge multiplicities (except one) equal to 3, which is almost 6-regular. We have no examples of 5-regular 5-edge-connected graphs with fewer than spanning trees, which is more than the corresponding number for 6-regular 6-edge-connected graphs. The analogous surprising phenomenon occurs for each higher odd edge connectivity and regularity.

We study limits of convergent sequences of string graphs, that is graphs with an intersection representation consisting of curves in the plane. We use these results to study the limiting behavior of a sequence of random string graphs. We also prove similar results for several related graph classes.

For a positive integer *k*, a *k*-*coloring* of a graph is a mapping such that whenever . The COLORING problem is to decide, for a given *G* and *k*, whether a *k*-coloring of *G* exists. If *k* is fixed (i.e., it is not part of the input), we have the decision problem *k*-COLORING instead. We survey known results on the computational complexity of COLORING and *k*-COLORING for graph classes that are characterized by one or two forbidden induced subgraphs. We also consider a number of variants: for example, where the problem is to extend a partial coloring, or where lists of permissible colors are given for each vertex.

Neumann-Lara (1985) and Škrekovski conjectured that every planar digraph with digirth at least three is 2-colorable, meaning that the vertices can be 2-colored without creating any monochromatic directed cycles. We prove a relaxed version of this conjecture: every planar digraph of digirth at least five is 2-colorable. The result also holds in the setting of list colorings.

We exhibit a close connection between hitting times of the simple random walk on a graph, the Wiener index, and related graph invariants. In the case of trees, we obtain a simple identity relating hitting times to the Wiener index. It is well known that the vertices of any graph can be put in a linear preorder so that vertices appearing earlier in the preorder are “easier to reach” by a random walk, but “more difficult to get out of.” We define various other natural preorders and study their relationships. These preorders coincide when the graph is a tree, but not necessarily otherwise. Our treatise is self-contained, and puts some known results relating the behavior or random walk on a graph to its eigenvalues in a new perspective.

A *dominating path* in a graph is a path *P* such that every vertex outside *P* has a neighbor on *P*. A result of Broersma from 1988 implies that if *G* is an *n*-vertex *k*-connected graph and , then *G* contains a dominating path. We prove the following results. The lengths of dominating paths include all values from the shortest up to at least . For , where *a* is a constant greater than 1/3, the minimum length of a dominating path is at most logarithmic in *n* when *n* is sufficiently large (the base of the logarithm depends on *a*). The preceding results are sharp. For constant *s* and , an *s*-vertex dominating path is guaranteed by when *n* is sufficiently large, but (where ) does not even guarantee a dominating set of size *s*. We also obtain minimum-degree conditions for the existence of a spanning tree obtained from a dominating path by giving the same number of leaf neighbors to each vertex.

The *minimum leaf number* ml(*G*) of a connected graph *G* is defined as the minimum number of leaves of the spanning trees of *G* if *G* is not hamiltonian and 1 if *G* is hamiltonian. We study nonhamiltonian graphs with the property for each or for each . These graphs will be called -leaf-critical *and l*-leaf-stable, respectively. It is far from obvious whether such graphs exist; for example, the existence of 3-leaf-critical graphs (that turn out to be the so-called hypotraceable graphs) was an open problem until 1975. We show that *l*-leaf-stable and *l*-leaf-critical graphs exist for every integer , moreover for *n* sufficiently large, planar *l*-leaf-stable and *l*-leaf-critical graphs exist on *n* vertices. We also characterize 2-fragments of leaf-critical graphs generalizing a lemma of Thomassen. As an application of some of the leaf-critical graphs constructed, we settle an open problem of Gargano et al. concerning spanning spiders. We also explore connections with a family of graphs introduced by Grünbaum in correspondence with the problem of finding graphs without concurrent longest paths.

In this article, we define and study a new family of graphs that generalizes the notions of line graphs and path graphs. Let *G* be a graph with no loops but possibly with parallel edges. An ℓ*-link* of *G* is a walk of *G* of length in which consecutive edges are different. The ℓ*-link graph* of *G* is the graph with vertices the ℓ-links of *G*, such that two vertices are joined by edges in if they correspond to two subsequences of each of μ -links of *G*. By revealing a recursive structure, we bound from above the chromatic number of ℓ-link graphs. As a corollary, for a given graph *G* and large enough ℓ, is 3-colorable. By investigating the shunting of ℓ-links in *G*, we show that the Hadwiger number of a nonempty is greater or equal to that of *G*. Hadwiger's conjecture states that the Hadwiger number of a graph is at least the chromatic number of that graph. The conjecture has been proved by Reed and Seymour (Eur J Combin 25(6) (2004), 873–876) for line graphs, and hence 1-link graphs. We prove the conjecture for a wide class of ℓ-link 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.

A graph is hypohamiltonian if it is not Hamiltonian, but the deletion of any single vertex gives a Hamiltonian graph. Until now, the smallest known planar hypohamiltonian graph had 42 vertices, a result due to Araya and Wiener. That result is here improved upon by 25 planar hypohamiltonian graphs of order 40, which are found through computer-aided generation of certain families of planar graphs with girth 4 and a fixed number of 4-faces. It is further shown that planar hypohamiltonian graphs exist for all orders greater than or equal to 42. If Hamiltonian cycles are replaced by Hamiltonian paths throughout the definition of hypohamiltonian graphs, we get the definition of hypotraceable graphs. It is shown that there is a planar hypotraceable graph of order 154 and of all orders greater than or equal to 156. We also show that the smallest planar hypohamiltonian graph of girth 5 has 45 vertices.

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*.

We show that the 4-coloring problem can be solved in polynomial time for graphs with no induced 5-cycle *C*_{5} and no induced 6-vertex path *P*_{6}

We prove that a graph *G* contains no induced -vertex path and no induced complement of a -vertex path if and only if *G* is obtained from 5-cycles and split graphs by repeatedly applying the following operations: substitution, split unification, and split unification in the complement, where split unification is a new class-preserving operation introduced here.

Let be a sequence of of nonnegative integers pairs. If a digraph *D* with satisfies and for each *i* with , then **d** is called a degree sequence of *D*. If *D* is a strict digraph, then **d** is called a strict digraphic sequence. Let be the collection of digraphs with degree sequence **d**. We characterize strict digraphic sequences **d**
for which there exists a strict strong digraph .

We prove that the number of 1-factorizations of a generalized Petersen graph of the type is equal to the *k*th Jacobsthal number when *k* is odd, and equal to when *k* is even. Moreover, we verify the list coloring conjecture for .

Let *H* be a given graph. A graph *G* is said to be *H*-free if *G* contains no induced copies of *H*. For a class of graphs, the graph *G* is -free if *G* is *H*-free for every . Bedrossian characterized all the pairs of connected subgraphs such that every 2-connected -free graph is hamiltonian. Faudree and Gould extended Bedrossian's result by proving the necessity part of the result based on infinite families of non-hamiltonian graphs. In this article, we characterize all pairs of (not necessarily connected) graphs such that there exists an integer *n*_{0} such that every 2-connected -free graph of order at least *n*_{0} is hamiltonian.

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.

We prove a decomposition theorem for the class of triangle-free graphs that do not contain a subdivision of the complete graph on four vertices as an induced subgraph. We prove that every graph of girth at least five in this class is 3-colorable.

A graph is *strongly even-cycle decomposable* if the edge set of every subdivision with an even number of edges can be partitioned into cycles of even length. We prove that several fundamental composition operations that preserve the property of being Eulerian also yield strongly even-cycle decomposable graphs. As an easy application of our theorems, we give an exact characterization of the set of strongly even-cycle decomposable cographs.

We determine the 2-color Ramsey number of a *connected*
triangle matching that is any connected graph containing *n* vertex disjoint triangles. We obtain that , somewhat larger than in the classical result of Burr, Erdős, and Spencer for a triangle matching, . The motivation is to determine the Ramsey number of the square of a cycle . We apply our Ramsey result for connected triangle matchings to show that the Ramsey number of an “almost” square of a cycle (a cycle of length *n* in which all but at most a constant number *c* of short diagonals are present) is asymptotic to .

In this article, we investigate the connectedness and the isomorphism problems for zig-zag products of two graphs. A sufficient condition for the zig-zag product of two graphs to be connected is provided, reducing to the study of the connectedness property of a new graph which depends only on the second factor of the graph product. We show that, when the second factor is a cycle graph, the study of the isomorphism problem for the zig-zag product is equivalent to the study of the same problem for the associated pseudo-replacement graph. The latter is defined in a natural way, by a construction generalizing the classical replacement product, and its degree is smaller than the degree of the zig-zag product graph. Two particular classes of products are studied in detail: the zig-zag product of a complete graph with a cycle graph, and the zig-zag product of a 4-regular graph with the cycle graph of length 4. Furthermore, an example coming from the theory of Schreier graphs associated with the action of self-similar groups is also considered: the graph products are completely determined and their spectral analysis is developed.

A graph *H* is *strongly immersed* in *G* if *H* is obtained from *G* by a sequence of vertex splittings (i.e., lifting some pairs of incident edges and removing the vertex) and edge removals. Equivalently, vertices of *H* are mapped to distinct vertices of *G* (*branch vertices*) and edges of *H* are mapped to pairwise edge-disjoint paths in *G*, each of them joining the branch vertices corresponding to the ends of the edge and not containing any other branch vertices. We describe the structure of graphs avoiding a fixed graph as a strong immersion. The theorem roughly states that a graph which excludes a fixed graph as a strong immersion has a tree-like decomposition into pieces glued together on small edge cuts such that each piece of the decomposition has a path-like linear decomposition isolating the high degree vertices.

We study the following independent set reconfiguration problem, called *TAR-Reachability*:
given two independent sets *I* and *J* of a graph *G*, both of size at least *k*, is it possible to transform *I* into *J* by adding and removing vertices one-by-one, while maintaining an independent set of size at least *k* throughout? This problem is known to be PSPACE-hard in general. For the case that *G* is a cograph on *n* vertices, we show that it can be solved in time , and that the length of a shortest reconfiguration sequence from *I* to *J* is bounded by (if it exists). More generally, we show that if is a graph class for which (i) TAR-Reachability can be solved efficiently, (ii) maximum independent sets can be computed efficiently, and which satisfies a certain additional property, then the problem can be solved efficiently for any graph that can be obtained from a collection of graphs in using disjoint union and complete join operations. Chordal graphs and claw-free graphs are given as examples of such a class .

A set *S* of vertices in a hypergraph *H* is strongly independent if no two vertices in *S* belong to a common edge. The strong independence number of *H*, denoted , is the maximum cardinality of a strongly independent set in *H*. The rank of *H* is the size of a largest edge in *H*. The hypergraph *H* is *k*-uniform if every edge of *H* has size *k*. The transversal number, denoted , of *H* is the minimum number of vertices that intersect every edge. Our main result is that for all , the strong independence ratio of a hypergraph *H* with rank *k* and maximum degree 3 satisfies and this bound is achieved for all . In particular, this bound is achieved for the Fano plane. As an application of our result, we show that if *H* is a *k*-uniform hypergraph on *n* vertices with *m* edges and with maximum degree 3 and vertices of degree 3, then . This improves a result due to Chvátal and McDiarmid [Combinatorica 12 (1992), 19–26] who proved that in the case when is even and *H* has maximum degree 3.