On signpost systems and connected graphs

By a signpost system we mean an ordered pair (W, P), where W is a finite nonempty set, P W × W × W and the following statements hold: if (u, v, w) P, then (v, u, u) P and (v, u, w) P, for all u, v, w W; if u v; then there exists r W such that (u, r, v) P, for all u, v W. We say that a signpost system (W, P) is smooth if the folowing statement holds for all u, v, x, y, z W: if (u, v, x), (u, v, z), (x, y, z) P, then (u, v, y) P. We say thay a signpost system (W, P) is simple if the following statement holds for all u, v, x, y W: if (u, v, x), (x, y, v) P, then (u, v, y), (x, y, u) P.By the underlying graph of a signpost system (W, P) we mean the graph G with V(G) = W and such that the following statement holds for all distinct u, v W: u and v are adjacent in G if and only if (u, v, v) P. The main result of this paper is as follows: If G is a graph, then the following three statements are equivalent: G is connected; G is the underlying graph of a simple smooth signpost system; G is the underlying graph of a smooth signpost system.Research was supported by Grant Agency of the Czech Republic, grant No. 401/01/0218.     

Distance-hereditary graphs are clique-perfect

In this paper, we show that the clique-transversal number τ_C(G) and the clique-independence number α_C(G) are equal for any distance-hereditary graph G. As a byproduct of proving that τ_C(G)=α_C(G), we give a linear-time algorithm to find a minimum clique-transversal set and a maximum clique-independent set simultaneously for distance-hereditary graphs.     

Convexities related to path properties on graphs

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.     

Triangle-free graphs with no six-vertex induced path

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

Equistable distance-hereditary graphs

A graph is called equistable when there is a non-negative weight function on its vertices such that a set S of vertices has total weight 1 if and only if S is maximal stable. We show that a necessary condition for a graph to be equistable is sufficient when the graph in question is distance-hereditary. This is used to design a polynomial-time recognition algorithm for equistable distance-hereditary graphs.     

On geodesic structures of weakly median graphs I. Decomposition and octahedral graphs

We prove that the non-trivial (finite or infinite) weakly median graphs which are undecomposable with respect to gated amalgamation and Cartesian multiplication are the 5-wheels, the subhyperoctahedra different from K₁, the path K_1,2 and the 4-cycle K_2,2, and the two-connected K₄- and K_1,1,3-free bridged graphs. These prime graphs are exactly the weakly median graphs which do not have any proper gated subgraphs other than singletons. For finite graphs, these results were already proved in [H.-J. Bandelt, V.C. Chepoi, The algebra of metric betweenness I: subdirect representation, retracts, and axiomatics of weakly median graphs, preprint, 2002]. A graph G is said to have the half-space copoint property (HSCP) if every non-trivial half-space of the geodesic convexity of G is a copoint at each of its neighbors. It turns out that any median graph has the HSCP. We characterize the weakly median graphs having the HSCP. We prove that the class of these graphs is closed under gated amalgamation and Cartesian multiplication, and we describe the prime and the finite regular elements of this class.     

Classification of reconfiguration graphs of shortest path graphs with no induced 4-cycles

For any graph $G$ with $a,b\in V\left(G\right)$, a shortest path reconfiguration graph can be formed with respect to $a$ and $b$; we denote such a graph as $S(G,a,b)$. The vertex set of $S(G,a,b)$ is the set of all shortest paths from $a$ to $b$ in $G$ while two vertices $U,W$ in $V\left(S(G,a,b)\right)$ are adjacent if and only if the vertex sets of the paths that represent $U$ and $W$ differ in exactly one vertex. In a recent paper (Asplund et al., 2018), it was shown that shortest path graphs with girth five or greater are exactly disjoint unions of even cycles and paths. In this paper, we extend this result by classifying all shortest path graphs with no induced 4-cycles.     

A new family of Geodesic transitive graphs

We present a new family of locally geodesic transitive graphs with arbitrarily large diameter and valencies, containing a particular case to be geodesic transitive. We also prove that it is a unique family in some generalised family of graphs.     

Claw-free graphs. III. Circular interval graphs

Construct a graph as follows. Take a circle, and a collection of intervals from it, no three of which have union the entire circle; take a finite set of points V from the circle; and make a graph with vertex set V in which two vertices are adjacent if they both belong to one of the intervals. Such graphs are “long circular interval graphs,” and they form an important subclass of the class of all claw-free graphs. In this paper we characterize them by excluded induced subgraphs. This is a step towards the main goal of this series, to find a structural characterization of all claw-free graphs.This paper also gives an analysis of the connected claw-free graphs G with a clique the deletion of which disconnects G into two parts both with at least two vertices.     

Dominating and large induced trees in regular graphs

Recently Chen et al. [Tree domination in graphs, Ars Combin. 73 (2004) 193-203] asked for characterizations of the class of graphs and the class of regular graphs that have an induced dominating tree, i.e. for which there exists a dominating set that induces a tree.We give a somewhat negative answer to their question by proving that the corresponding decision problems are NP-complete. Furthermore, we prove essentially best-possible lower bounds on the maximum order of induced trees in connected cacti of maximum degree 3 and connected cubic graphs.Finally, we give a forbidden induced subgraph condition for the existence of induced dominating trees.     

Path factors in cubic graphs

Let ? be a set of connected graphs. An ?‐factor of a graph is its spanning subgraph such that each component is isomorphic to one of the members in ?. Let P_k denote the path of order k. Akiyama and Kano have conjectured that every 3‐connected cubic graph of order divisible by 3 has a {P₃}‐factor. Recently, Kaneko gave a necessary and sufficient condition for a graph to have a {P₃, P₄, P₅}‐factor. As a corollary, he proved that every cubic graph has a {P₃, P₄, P₅}‐factor. In this paper, we prove that every 2‐connected cubic graph of order at least six has a {P_k ∣ k ≥ , 6}‐factor, and hence has a {P₃, P₄}‐factor. © 2002 Wiley Periodicals, Inc. J Graph Theory 39: 188–193, 2002; DOI 10.1002/jgt.10022     

On the strong chromatic index and maximum induced matching of tree-cographs,permutation graphs and chordal bipartite graphs

We show that there exist linear-time algorithms that compute the strong chromatic index and a maximum induced matching of tree-cographs when the decomposition tree is a part of the input. We also show that there exist efficient algorithms for the strong chromatic index of (bipartite) permutation graphs and of chordal bipartite graphs.     

(k,+)-distance-hereditary graphs

In this work we introduce, characterize, and provide algorithmic results for (k,+)-distance-hereditary graphs, k0. These graphs can be used to model interconnection networks with desirable connectivity properties; a network modeled as a (k,+)-distance-hereditary graph can be characterized as follows: if some nodes have failed, as long as two nodes remain connected, the distance between these nodes in the faulty graph is bounded by the distance in the non-faulty graph plus an integer constant k. The class of all these graphs is denoted by DH(k,+). By varying the parameter k, classes DH(k,+) include all graphs and form a hierarchy that represents a parametric extension of the well-known class of distance-hereditary graphs.     

On the inducibility of oriented graphs on four vertices

We consider the problem of determining the inducibility (maximum possible asymptotic density of induced copies) of oriented graphs on four vertices. We provide exact values for more than half of the graphs, and very close lower and upper bounds for all the remaining ones. It occurs that, for some graphs, the structure of extremal constructions maximizing density of its induced copies is very sophisticated and complex.     

Locally connected spanning trees in strongly chordal graphs and proper circular-arc graphs

A locally connected spanning tree of a graph G is a spanning tree T of G such that the set of all neighbors of v in T induces a connected subgraph of G for every v∈V(G). The purpose of this paper is to give linear-time algorithms for finding locally connected spanning trees on strongly chordal graphs and proper circular-arc graphs, respectively.     

Infinite paths in planar graphs V, 3‐indivisible graphs

We prove Nash‐Williams' conjecture that every 4‐connected, 3‐indivisible, infinite, planar graph contains a spanning 2‐way infinite path. A graph is said to be 3‐indivisible if the deletion of any finite set of vertices results in at most two infinite components. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 275–312, 2008