Search

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. Beisegel, Chudovsky, Gurvich, Milanic, and Servatius (WADS 2019) 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 before). The same year Bonamy, Defrain, Hatzel, and Thiebaut proved the conjecture for all $k$. Here we strengthen their result and show that every induced path can be shifted to an avoidable one. We also prove analogous results for the non-induced case and for the case of walks, and show that the statement cannot be extended to trails or to isometric paths.

Given an edge-weighted graph G and two distinct vertices s and t of G, the next-to-shortest path problem asks for a path from s to t of minimum length among all paths from s to t except the shortest ones. In this article, we consider the version where G is directed and all edge weights are positive. Some properties of the requested path are derived when G is an arbitrary digraph. In addition, if G is planar, an On3-time algorithm is proposed, where n is the number of vertices of G. © 2015 Wiley Periodicals, Inc. NETWORKS, Vol. 653, 205-211 2015

Let be the class of all graphs with no induced four-edge path or four-edge antipath. Hayward and Nastos [6] conjectured that every prime graph in not isomorphic to the cycle of length five is either a split graph or contains a certain useful arrangement of simplicial and antisimplicial vertices. In this article, we give a counterexample to their conjecture, and prove a slightly weaker version. Additionally, applying a result of the first author and Seymour [1] we give a short proof of Fouquet's result [3] on the structure of the subclass of bull-free graphs contained in .

In 1966, Gallai conjectured that for any simple, connected graph G having n vertices, there is a path-decomposition of G having at most paths. In this article, we show that for any simple graph G having girth , there is a path-decomposition of G having at most paths, where is the number of vertices of odd degree in G and is the number of nonisolated vertices of even degree in G.

Erdős and Hajnal [Discrete Math 25 (1989), 37–52] conjectured that, for any graph H, every graph on n vertices that does not have H as an induced subgraph contains a clique or a stable set of size nɛ(H) for some ɛ(H)>0. The Conjecture 1. known to be true for graphs H with |V(H)|≤4. One of the two remaining open cases on five vertices is the case where H is a four-edge path, the other case being a cycle of length five. In this article we prove that every graph on n vertices that does not contain a four-edge path or the complement of a five-edge path as an induced subgraph contains either a clique or a stable set of size at least n1/6. © 2011 Wiley Periodicals, Inc. J Graph Theory (This research was performed while the author was at Columbia University. © 2012 Wiley Periodicals, Inc.)

In the Star System problem we are given a set system and asked whether it is realizable by the multi-set of closed neighborhoods of some graph, i.e. given subsets S1, S2, …, Sn of an n-element set V does there exist a graph G = (V, E) with {N[v]: v∈V} = {S1, S2, …, Sn}? For a fixed graph H the H-free Star System problem is a variant of the Star System problem where it is asked whether a given set system is realizable by closed neighborhoods of a graph containing no H as an induced subgraph. We study the computational complexity of the H-free Star System problem. We prove that when H is a path or a cycle on at most four vertices the problem is polynomial time solvable. In complement to this result, we show that if H belongs to a certain large class of graphs the H-free Star System problem is NP-complete. In particular, the problem is NP-complete when H is either a cycle or a path on at least five vertices. This yields a complete dichotomy for paths and cycles. Copyright © 2010 John Wiley & Sons, Ltd. 68:113-124, 2011

Suppose that G is a bipartite graph with its partite sets of equal size. G is said to be strongly Hamiltonian-laceable if there is a Hamiltonian path between every two vertices that belong to different partite sets and there is a path of (maximal) length N - 2 between every two vertices that belong to the same partite set, where N is the order of G. In other words, a strongly Hamiltonian-laceable graph has a longest path between every two of its vertices. In this paper, we show that the star graphs with dimension four or larger are strongly Hamiltonian-laceable. © 2000 john Wiley & Sons, Inc.

The wing-graph W(G) of a graph G has all edges of G as its vertices; two edges of G are adjacent in W(G) if they are the nonincident edges (called wings) of an induced path on four vertices in G. Hoang conjectured that if W(G) has no induced cycle of odd length at least five, then G is perfect. As a partial result towards Hoang's conjecture we prove that if W(G) is triangulated, then G is perfect. © 1997 John Wiley & Sons, Inc.

The path layer matrix (or path degree sequence) of a graph G contains quantitative information about all possible paths in G. The entry (i,j) of this matrix is the number of paths in G having initial vertex i and length j. It is known that there are cubic graphs on 62 vertices having the same path layer matrix (A. A. Dobrynin. J Graph Theory 17 (1993) 1–4). A new upper bound of 36 vertices for the least order of such cubic graphs is established. This bound is realized by cubic graphs without cut-vertices. © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 177–182, 2001

In this article we study asymptotic properties of the class of graphs not containing a fixed graph H as an induced subgraph. In particular we show that the number Forbn★(H) of such graphs on n vertices is essentially determined by the number of subgraphs of a single graph. This implies that ***image*** Where t(H) is a graph-theoretic parameter generalizing the chromatic number and the clique covering number. This result complements a theorem of Erdos, Frankl, and Rodl [2] who showed that the number Forbn(H) of graphs on n vertices which do not contain H as a weak subgraph is given by ***image*** © 1992 Wiley Periodicals, Inc.

In this note we determine the structure of “almost all” graphs not containing a quadrilateral (i.e., a cycle of length four) as an induced subgraph. In particular, it turns out that there are asymptotically twice as many graphs not containing an induced quadrilateral than there are bipartite graphs.

The Steiner distance of a set S of vertices in a connected graph G is the minimum size among all connected subgraphs of G containing S. For n ≥ 2, the n-eccentricity en(ν) of a vertex ν of a graph G is the maximum Steiner distance among all sets S of n vertices of G that contains ν. The n-diameter of G is the maximum n-eccentricity among the vertices of G while the n-radius of G is the minimum n-eccentricity. The n-center of G is the subgraph induced by those vertices of G having minimum n-eccentricity. It is shown that every graph is the n-center of some graph. Several results on the n-center of a tree are established. In particular, it is shown that the n-center of a tree is a tree and those trees that are n-centers of trees are characterized.

The following theorem is proved: Let G be a graph of even order. Assume that there exists a connected spanning subgraph F of G such that for every set U of four vertices in G, if the subgraph of F induced by U is a star, then the subgraph of G induced by U is complete. Then G has a 1-factor. The above theorem is derived from another sufficient condition for the existence of a 1-factor, which is also proved in this paper (Lemma 1).

We prove that if K is an undirected, simple, connected graph of even order which is of class one, regular of degree p ≥ 2 and such that the subgraph induced by any three vertices is either connected or null, then any graph G obtained from K by splitting any vertex is p-critical. We find that various constructions of critical graphs by S. Fiorini are special cases of a corollary of this result.

A graph G is locally n-connected, n ≥ 1, if the subgraph induced by the neighborhood of each vertex is n-connected. We prove that every connected, locally 2-connected graph containing no induced subgraph isomorphic to K1,3 is panconnected.

The Hamiltonian path graph H(G) of a graph G is that graph having the same vertex set as G and in which two vertices u and v are adjacent if and only if G contains a Hamiltonian u-v path. A characterization of Hamiltonian graphs isomorphic to their Hamiltonian path graphs is presented.

Separation properties for some intrinsic convexities of graphs are investigated. The most natural convexities defined on a graph are the induced path convexity and the geodesic convexity. A set A of vertices is convex with respect to the former convexity if A contains every induced path connecting two vertices of A. In particular, a characterization of those graphs is given in which all such convex sets are the intersections of halfspaces (i.e., convex sets with convex complements).