Search

In this paper, we establish the induced path polynomials of graphs resulting from the join and corona of two connected graphs. [ABSTRACT FROM AUTHOR]

We show that for any d=d(n) with d0(ϵ)≤d=o(n), with high probability, the size of a largest induced cycle in the random graph G(n,d/n) is (2±ϵ)ndlogd. This settles a long‐standing open problem in random graph theory. [ABSTRACT FROM AUTHOR]

An extension of an induced path P in a graph G is an induced path P′ such that deleting the endpoints of P′ results in P. An induced path in a graph is said to be avoidable if each of its extensions is contained in an induced cycle. In 2019, Beisegel, Chudovsky, Gurvich, Milanič, and Servatius conjectured that every graph that contains an induced k‐vertex path also contains an avoidable induced path of the same length, and proved the result for k=2. The case k=1 was known much earlier, due to a work of Ohtsuki, Cheung, and Fujisawa in 1976. The conjecture was proved for all k in 2020 by Bonamy, Defrain, Hatzel, and Thiebaut. In the present paper, using a similar approach, we strengthen their result from a reconfiguration point of view. Namely, we show that in every graph, each induced path can be transformed to an avoidable one by a sequence of shifts, where two induced k‐vertex paths are shifts of each other if their union is an induced path with k+1 vertices. We also obtain analogous results for not necessarily induced paths and for walks. In contrast, the statement cannot be extended to trails or to isometric paths. [ABSTRACT FROM AUTHOR]

An induced path factor of a graph G is a set of induced paths in G with the property that every vertex of G is in exactly one of the paths. The induced path numberρ(G) of G is the minimum number of paths in an induced path factor of G. We show that if G is a connected cubic graph on n>6 vertices, then ρ(G)⩽(n−1)/3. Fix an integer k⩾3. For each n, define ℳn to be the maximum value of ρ(G) over all connected k‐regular graphs G on n vertices. As n→∞ with nk even, we show that ck=lim(ℳn/n) exists. We prove that 5/18⩽c3⩽1/3 and 3/7⩽c4⩽1/2 and that ck=12−O(k−1) for k→∞. [ABSTRACT FROM AUTHOR]

The snake-in-the-box problem asks for the maximum length of a chordless path (also called snake) in the $$n$$ -cube. A computer-aided approach for classifying long snakes in the $$n$$ -cube is here developed. A recursive construction and isomorph rejection via canonical augmentation form the core of the approach. The snake-in-the box problem has earlier been solved for $$n\le 7$$ ; that work is here extended by showing that the longest snake in the 8-cube has 98 edges. [ABSTRACT FROM AUTHOR]

The Parity Path problem is to decide if a given graph contains both an induced path of odd length and an induced path of even length between two specified vertices. In the related problems Odd Induced Path and Even Induced Path, the goal is to determine whether an induced path of odd, respectively even, length between two specified vertices exists. Although all three problems are NP-complete in general, we show that they can be solved in $\mathcal{O}(n^{5})$ time for the class of claw-free graphs. Two vertices s and t form an even pair in G if every induced path from s to t in G has even length. Our results imply that the problem of deciding if two specified vertices of a claw-free graph form an even pair, as well as the problem of deciding if a given claw-free graph has an even pair, can be solved in $\mathcal{O}(n^{5})$ time and $\mathcal{O}(n^{7})$ time, respectively. We also show that we can decide in $\mathcal{O}(n^{7})$ time whether a claw-free graph has an induced cycle of given parity through a specified vertex. Finally, we show that a shortest induced path of given parity between two specified vertices of a claw-free perfect graph can be found in $\mathcal {O}(n^{7})$ time. [ABSTRACT FROM AUTHOR]

The k- in-a-Path problem is to test whether a graph contains an induced path spanning k given vertices. This problem is NP-complete in general graphs, already when k=3. We show how to solve it in polynomial time on claw-free graphs, when k is an arbitrary fixed integer not part of the input. As a consequence, also the k- Induced Disjoint Paths and the k- in-a-Cycle problem are solvable in polynomial time on claw-free graphs for any fixed k. The first problem has as input a graph G and k pairs of specified vertices ( s, t) for i=1,..., k and is to test whether G contain k mutually induced paths P such that P connects s and t for i=1,..., k. The second problem is to test whether a graph contains an induced cycle spanning k given vertices. When k is part of the input, we show that all three problems are NP-complete, even for the class of line graphs, which form a subclass of the class of claw-free graphs. [ABSTRACT FROM AUTHOR]

For a finite poset P = ( V, ≤ ), let ${\cal B}_s(P)$ consist of all triples ( x, y, z) ∈ V such that either x < y < z or z < y < x. Similarly, for every finite, simple, and undirected graph G = ( V, E), let ${\cal B}_s(G)$ consist of all triples ( x, y, z) ∈ V such that y is an internal vertex on an induced path in G between x and z. The ternary relations ${\cal B}_s(P)$ and ${\cal B}_s(G)$ are well-known examples of so-called strict betweennesses. We characterize the pairs ( P, G) of posets P and graphs G on the same ground set V which induce the same strict betweenness relation ${\cal B}_s(P)={\cal B}_s(G)$. [ABSTRACT FROM AUTHOR]