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]

Abstract Given a graph G = (V , E) whose vertices have been properly coloured, we say that a path in G is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai–Roy–Vitaver Theorem that every properly coloured graph contains a colourful path on χ (G) vertices. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on χ (G) vertices and prove its correctness when the girth of G is at least χ (G). Recent work on this conjecture by Gyárfás and Sárközy, and Scott and Seymour has shown the existence of a function f such that if χ (G) ≥ f (k) , then an induced colourful path on k vertices is guaranteed to exist in any properly coloured triangle-free graph G. [ABSTRACT FROM AUTHOR]

The graphs with no five-vertex induced path are still not understood. But in the triangle-free case, we can do this and one better; we give an explicit construction for all triangle-free graphs with no six-vertex induced path. Here are three examples: the 16-vertex Clebsch graph, the graph obtained from an 8-cycle by making opposite vertices adjacent, and the graph obtained from a complete bipartite graph by subdividing a perfect matching. We show that every connected triangle-free graph with no six-vertex induced path is an induced subgraph of one of these three (modulo some twinning and duplication). [ABSTRACT FROM AUTHOR]

Given a graph G = ( V , E ) whose vertices have been properly coloured, we say that a path in G is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai-Roy Theorem that every properly coloured graph contains a colourful path on χ ( G ) vertices. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on χ ( G ) vertices and prove its correctness when the girth of G is at least χ ( G ) . Recent work on this conjecture by Gyárfás and Sárközy, and Scott and Seymour has shown the existence of a function f such that if χ ( G ) ≥ f ( k ) , then an induced colourful path on k vertices is guaranteed to exist in any properly coloured triangle-free graph G . [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]

Abstract: Let and be the geodesic and induced path intervals between and in a connected graph , respectively. The following three betweenness axioms are considered for a set and : [(i)] ; [(ii)] ; [(iii)] . We characterize the class of graphs for which satisfies (i), the class for which satisfies (ii) and the class for which or satisfies (iii). The characterization is given in terms of forbidden induced subgraphs. It turns out that the class of graphs for which satisfies (i) is a proper subclass of distance hereditary graphs and the class for which satisfies (ii) is a proper superclass of distance hereditary graphs. We also give an axiomatic characterization of chordal and Ptolemaic graphs. [Copyright &y& Elsevier]

Abstract: Many recognition problems for special classes of graphs and cycles can be reduced to finding and listing induced paths and cycles in a graph. We design algorithms to list all ’s in time, and for all ’s in time, where , respectively, , are the number of ’s, respectively, ’s, of a graph . We also provide an algorithm to find a , , in time if is odd, and if is even. As applications of our findings, we give algorithms to recognize quasi-triangulated graphs and brittle graphs. Our algorithms’ time bounds are incomparable with previously known algorithms. [Copyright &y& Elsevier]

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]

Abstract: The geodesic interval function of a connected graph allows an axiomatic characterization involving axioms on the function only, without any reference to distance, as was shown by Nebeský . Surprisingly, Nebeský  showed that, if no further restrictions are imposed, the induced path function of a connected graph does not allow such an axiomatic characterization. Here consists of the set of vertices lying on the induced paths between and . This function is a special instance of a transit function. In this paper we address the question what kind of restrictions could be imposed to obtain axiomatic characterizations of . The function satisfies betweenness if , with , implies and implies . It is monotone if implies . In the case where we restrict ourselves to functions that satisfy betweenness, or monotonicity, we are able to provide such axiomatic characterizations of by transit axioms only. The graphs involved can all be characterized by forbidden subgraphs. [Copyright &y& Elsevier]

Abstract: An ordered pair is called a signpost system if is a finite nonempty set, , and the following axioms hold for all : (1) if , then ; (2) if , then ; (3) if , then there exists such that . (If is a (finite) connected graph with vertex set and distance function , then together with the set of all ordered triples of vertices in such that and is an example of a signpost system). If is a signpost system and is a graph, then is called the underlying graph of if and if and only if (for all ). It is possible to say that a signpost system shows a way how to travel in its underlying graph. The following result is proved: Let be a signpost system and let denote the underlying graph of . Then is connected and every induced path in is a geodesic in if and only if satisfies axioms (4)–(8) stated in this paper; note that axioms (4)–(8)–similarly as axioms (1)–(3)–can be formulated in the language of the first-order logic. [Copyright &y& Elsevier]

Abstract: We show that deciding if a graph without induced paths on nine vertices can be colored with 4 colors is an NP-complete problem, improving a previous NP-completeness result proved by Woeginger and Sgall in 2001. The complexity of 4-coloring graphs without induced paths on five vertices remains open. We show that deciding if a graph without induced paths or cycles on five vertices can be colored with 4 colors can be done in polynomial time. A step in our algorithm uses the well-known and deep fact due to Grötschel, Lovász and Schrijver stating that perfect graphs can be optimally colored in polynomial time. [Copyright &y& Elsevier]

Abstract: We give a characterization, in terms of forbidden induced subgraphs, of those graphs in which every connected induced subgraph has a dominating induced path on at most k vertices (). We show, in particular, that means precisely the class of domination-reducible graphs, whose original definition applied four types of structural reduction. [Copyright &y& Elsevier]

Abstract: In a graph, an induced path is a path in which a vertex is adjacent to another vertex if and only if . An induced-path partition of a graph is a collection of vertex-disjoint induced paths that cover all vertices of the graph. The induced-path-partition problem is to determine the minimum cardinality of an induced-path partition of a graph. This paper presents an -time algorithm for the induced-path-partition problem on graphs whose blocks are complete graphs, cycles or complete bipartite graphs. [Copyright &y& Elsevier]

Abstract: Consider the following problem, which we call “Chordless path through three vertices” or CP3V, for short: Given a simple undirected graph , a positive integer k, and three distinct vertices s, t, and , is there a chordless path of length at most k from s via to t in G? In a chordless path, no two vertices are connected by an edge that is not in the path. Alternatively, one could say that the subgraph induced by the vertex set of the path in G is the path itself. The problem has arisen in the context of service deployment in communication networks. We resolve the parametric complexity of CP3V by proving it -complete with respect to its natural parameter k. Our reduction extends to a number of related problems about chordless paths and cycles. In particular, deciding on the existence of a single directed chordless -path in a digraph is also -complete with respect to the length of the path. [Copyright &y& Elsevier]

Abstract: A feasible family of paths in a connected graph G is a family that contains at least one path between any pair of vertices in G. Any feasible path family defines a convexity on G. Well-known instances are: the geodesics, the induced paths, and all paths. We propose a more general approach for such ‘path properties’. We survey a number of results from this perspective, and present a number of new results. We focus on the behaviour of such convexities on the Cartesian product of graphs and on the classical convexity invariants, such as the Carathéodory, Helly and Radon numbers in relation with graph invariants, such as the clique number and other graph properties. [Copyright &y& Elsevier]

The induced path transit function J(u,v) in a graph consists of the set of all vertices lying on any induced path between the vertices u and v. A transit function J satisfies monotone axiom if x,y∈J(u,v) implies J(x,y)⊆J(u,v). A transit function J is said to satisfy the Peano axiom if, for any u,v,w∈V, x∈J(v,w), y∈J(u,x), there is a z∈J(u,v) such that y∈J(w,z). These two axioms are equivalent for the induced path transit function of a graph. Planar graphs for which the induced path transit function satisfies the monotone axiom are characterized by forbidden induced subgraphs. [Copyright &y& Elsevier]

The induced path interval J(u,v) consists of the vertices on the induced paths between u and v in a connected graph G. Differences in properties with the geodesic interval are studied. Those graphs are characterized, in which the induced path intervals define a proper betweenness. The intersection of the induced path intervals between the pairs of a triple, in general, consists of a big chunk of vertices. The graphs, in which this intersection consists of at most one vertex, for each triple of vertices, are characterized by forbidden subgraphs. [Copyright &y& Elsevier]

We give a polynomial-time algorithm that, with input a graph G and two vertices u , v of G , decides whether there is an induced u v -path that is longer than the shortest u v -path. [ABSTRACT FROM AUTHOR]

Abstract: A dominating set of a graph is a set such that each vertex is either in the set or adjacent to a vertex in the set. We show that if is an -vertex maximal outerplanar graph with having vertices of degree , then has a dominating set of size at most , by a simple coloring method. [Copyright &y& Elsevier]