Hamiltonian path graphs

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.     

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.     

Outerplanar and Planar Oriented Cliques

The clique number of an undirected graph G is the maximum order of a complete subgraph of G and is a well‐known lower bound for the chromatic number of G. Every proper k‐coloring of G may be viewed as a homomorphism (an edge‐preserving vertex mapping) of G to the complete graph of order k. By considering homomorphisms of oriented graphs (digraphs without cycles of length at most 2), we get a natural notion of (oriented) colorings and oriented chromatic number of oriented graphs. An oriented clique is then an oriented graph whose number of vertices and oriented chromatic number coincide. However, the structure of oriented cliques is much less understood than in the undirected case. In this article, we study the structure of outerplanar and planar oriented cliques. We first provide a list of 11 graphs and prove that an outerplanar graph can be oriented as an oriented clique if and only if it contains one of these graphs as a spanning subgraph. Klostermeyer and MacGillivray conjectured that the order of a planar oriented clique is at most 15, which was later proved by Sen. We show that any planar oriented clique on 15 vertices must contain a particular oriented graph as a spanning subgraph, thus reproving the above conjecture. We also provide tight upper bounds for the order of planar oriented cliques of girth k for all .     

A common generalization of line graphs and clique graphs

Both the line graph and the clique graph are defined as intersection graphs of certain families of complete subgraphs of a graph. We generalize this concept. By a k-edge of a graph we mean a complete subgraph with k vertices or a clique with fewer than k vertices. The k-edge graph Δ_k(G) of a graph G is defined as the intersection graph of the set of all k-edges of G. The following three problems are investigated for k-edge graphs. The first is the characterization problem. Second, sets of graphs closed under the k-edge graph operator are found. The third problem is the question of convergence: What happens to a graph if we take iterated k-edge graphs?     

On the tree representation of chordal graphs

We introduce the notion of the boundary clique and the k-overlap clique graph and prove the following: Every incomplete chordal graph has two nonadjacent simplicial vertices lying in boundary cliques. An incomplete chordal graph G is k-connected if and only if the k-overlap clique graph g_k(G) is connected. We give an algorithm to construct a clique tree of a connected chordal graph and characterize clique trees of connected chordal graphs using the algorithm.     

Inequalities for the Grundy chromatic number of graphs

The Grundy (or First-Fit) chromatic number of a graph G is the maximum number of colors used by the First-Fit coloring of the graph G. In this paper we give upper bounds for the Grundy number of graphs in terms of vertex degrees, girth, clique partition number and for the line graphs. Next we show that if the Grundy number of a graph is large enough then the graph contains a subgraph of prescribed large girth and Grundy number.     

Finding a minimum path cover of a distance-hereditary graph in polynomial time

A path cover of a graph G=(V,E) is a set of pairwise vertex-disjoint paths such that the disjoint union of the vertices of these paths equals the vertex set V of G. The path cover problem is, given a graph, to find a path cover having the minimum number of paths. The path cover problem contains the Hamiltonian path problem as a special case since finding a path cover, consisting of a single path, corresponds directly to the Hamiltonian path problem. A graph is a distance-hereditary graph if each pair of vertices is equidistant in every connected induced subgraph containing them. The complexity of the path cover problem on distance-hereditary graphs has remained unknown. In this paper, we propose the first polynomial-time algorithm, which runs in O(|V|⁹) time, to solve the path cover problem on distance-hereditary graphs.     

On self-clique graphs with given clique sizes, II

The clique graph of a graph G is the graph obtained by taking the cliques of G as vertices, and two vertices are adjacent if and only if the corresponding cliques have a non-empty intersection. A graph is self-clique if it is isomorphic to its clique graph. We give a new characterization of the set of all connected self-clique graphs having all cliques but two of size 2.     

Graph powers and k-ordered Hamiltonicity

It is known that if G is a connected simple graph, then G³ is Hamiltonian (in fact, Hamilton-connected). A simple graph is k-ordered Hamiltonian if for any sequence v₁, v₂,…,v_k of k vertices there is a Hamiltonian cycle containing these vertices in the given order. In this paper, we prove that if k?4, then G^⌊3k/2⌋-2 is k-ordered Hamiltonian for every connected graph G on at least k vertices. By considering the case of the path graph P_n, we show that this result is sharp. We also give a lower bound on the power of the cycle C_n that guarantees k-ordered Hamiltonicity.     

The disjunctive domination number of a graph

Abstract

For a positive integer b, we define a set S of vertices in a graph G as a b-disjunctive dominating set if every vertex not in S is adjacent to a vertex of S or has at least b vertices in S at distance 2 from it. The b-disjunctive domination number is the minimum cardinality of such a set. This concept is motivated by the concepts of distance domination and exponential domination. In this paper, we start with some simple results, then establish bounds on the parameter especially for regular graphs and claw-free graphs. We also show that determining the parameter is NP-complete, and provide a linear-time algorithm for trees.     

Opposition graphs are strict quasi-parity graphs

An opposition graph is a graph whose edges can be acyclically oriented in such a way that every chordless path on four vertices has its extreme edges both pointing in or pointing out. A strict quasi-parity graph is a graphG such that every induced subgraphH ofG either is a clique or else contains a pair of vertices which are not endpoints of an odd (number of edges) chordless path ofH. The perfection of opposition graphs and strict quasi-parity graphs was established respectively by Olariu and Meyniel. We show here that opposition graphs are strict quasi-parity graphs.The second author acknowledges the support of the Air Force Office of Scientific Research under grant number AFOSR 0271 to Rutgers University.     

Safe separators for treewidth

A set of vertices S⊆V is called a safe separator for treewidth, if S is a separator of G, and the treewidth of G equals the maximum of the treewidth over all connected components W of G-S of the graph, obtained by making S a clique in the subgraph of G, induced by W∪S. We show that such safe separators are a very powerful tool for preprocessing graphs when we want to compute their treewidth. We give several sufficient conditions for separators to be safe, allowing such separators, if existing, to be found in polynomial time. In particular, every inclusion minimal separator of size one or two is safe, every minimum separator of size three that does not split off a component with only one vertex is safe, and every inclusion minimal separator that is an almost clique is safe; an almost clique is a set of vertices W such that there is a v∈W with W-{v} a clique. We report on experiments that show significant reductions of instance sizes for graphs from probabilistic networks and frequency assignment.     

On constructible graphs,locally Helly graphs,and convexity

A (finite or infinite) graph G is constructible if there exists a well‐ordering ≤ of its vertices such that for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Particular constructible graphs are Helly graphs and connected bridged graphs. In this paper we study a new class of constructible graphs, the class of locally Helly graphs. A graph G is locally Helly if, for every pair (x,y) of vertices of G whose distance is d ≥ 2, there exists a vertex whose distance to x is d ? 1 and which is adjacent to y and to all neighbors of y whose distance to x is at most d. Helly graphs are locally Helly, and the converse holds for finite graphs. Among different properties we prove that a locally Helly graph is strongly dismantable, hence cop‐win, if and only if it contains no isometric rays. We show that a locally Helly graph G is finitely Helly, that is, every finite family of pairwise non‐disjoint balls of G has a non‐empty intersection. We give a sufficient condition by forbidden subgraphs so that the three concepts of Helly graphs, of locally Helly graphs and of finitely Helly graphs are equivalent. Finally, generalizing different results, in particular those of Bandelt and Chepoi 1 about Helly graphs and bridged graphs, we prove that the Helly number h(G) of the geodesic convexity in a constructible graph G is equal to its clique number ω(G), provided that ω(G) is finite. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 280–298, 2003     

Graphs satisfying inequality θ(G)θ(G)

In this paper, we study the edge clique cover number of squares of graphs. More specifically, we study the inequality θ(G²)θ(G) where θ(G) is the edge clique cover number of a graph G. We show that any graph G with at most θ(G) vertices satisfies the inequality. Among the graphs with more than θ(G) vertices, we find some graphs violating the inequality and show that dually chordal graphs and power-chordal graphs satisfy the inequality. Especially, we give an exact formula computing θ(T²) for a tree T.     

Subspace Inclusion Graph of a Vector Space

In this paper, the authors introduce a graph structure, called subspace inclusion graph ?n(𝕍) on a finite dimensional vector space 𝕍 where the vertex set is the collection of nontrivial proper subspaces of a vector space and two vertices are adjacent if one is contained in other. The diameter, girth, clique number, and chromatic number of ?n(𝕍) are studied. It is shown that two subspace inclusion graphs are isomorphic if and only if the base vector spaces are isomorphic. Finally, some properties of subspace inclusion graph are studied when the base field is finite.     

Perfect Matchings in Balanced Hypergraphs – A Combinatorial Approach

Our topic is an extension of the following classical result of Hall to hypergraphs: A bipartite graph G contains a perfect matching if and only if for each independent set X of vertices, at least |X| vertices of G are adjacent to some vertex of X. Berge generalized the concept of bipartite graphs to hypergraphs by defining a hypergraph G to be balanced if each odd cycle in G has an edge containing at least three vertices of the cycle. Based on this concept, Conforti, Cornuéjols, Kapoor, and Vušković extended Hall's result by proving that a balanced hypergraph G contains a perfect matching if and only if for any disjoint sets A and B of vertices with |A| > |B|, there is an edge in G containing more vertices in A than in B (for graphs, the latter condition is equivalent to the latter one in Hall's result). Their proof is non-combinatorial and highly based on the theory of linear programming. In the present paper, we give an elementary combinatorial proof. Received April 29, 1997     

Clique-critical graphs: Maximum size and recognition

The clique graph of G, K(G), is the intersection graph of the family of cliques (maximal complete sets) of G. Clique-critical graphs were defined as those whose clique graph changes whenever a vertex is removed. We prove that if G has m edges then any clique-critical graph in K^-1(G) has at most 2m vertices, which solves a question posed by Escalante and Toft [On clique-critical graphs, J. Combin. Theory B 17 (1974) 170-182]. The proof is based on a restatement of their characterization of clique-critical graphs. Moreover, the bound is sharp. We also show that the problem of recognizing clique-critical graphs is NP-complete.     

List Homomorphisms and Circular Arc Graphs

G , H, and lists , a list homomorphism of G to H with respect to the lists L is a mapping , such that for all , and for all . The list homomorphism problem for a fixed graph H asks whether or not an input graph G together with lists , , admits a list homomorphism with respect to L. We have introduced the list homomorphism problem in an earlier paper, and proved there that for reflexive graphs H (that is, for graphs H in which every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP-complete otherwise. Here we consider graphs H without loops, and find that the problem is closely related to circular arc graphs. We show that the list homomorphism problem is polynomial time solvable if the complement of H is a circular arc graph of clique covering number two, and is NP-complete otherwise. For the purposes of the proof we give a new characterization of circular arc graphs of clique covering number two, by the absence of a structure analogous to Gallai's asteroids. Both results point to a surprising similarity between interval graphs and the complements of circular arc graphs of clique covering number two. Received: July 22, 1996/Revised: Revised June 10, 1998     

Perfect Graphs with No Balanced Skew‐Partition are 2‐Clique‐Colorable

A graph G is perfect if for all induced subgraphs H of G, . A graph G is Berge if neither G nor its complement contains an induced odd cycle of length at least five. The Strong Perfect Graph Theorem [9] states that a graph is perfect if and only if it is Berge. The Strong Perfect Graph Theorem was obtained as a consequence of a decomposition theorem for Berge graphs [M. Chudnovsky, Berge trigraphs and their applications, PhD thesis, Princeton University, 2003; M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas, The strong perfect graph theorem, Ann Math 164 (2006), 51–229.], and one of the decompositions in this decomposition theorem was the “balanced skew‐partition.” A clique‐coloring of a graph G is an assignment of colors to the vertices of G in such a way that no inclusion‐wise maximal clique of G of size at least two is monochromatic, and the clique‐chromatic number of G, denoted by , is the smallest number of colors needed to clique‐color G. There exist graphs of arbitrarily large clique‐chromatic number, but it is not known whether the clique‐chromatic number of perfect graphs is bounded. In this article, we prove that every perfect graph that does not admit a balanced skew‐partition is 2‐clique colorable. The main tool used in the proof is a decomposition theorem for “tame Berge trigraphs” due to Chudnovsky et al. ( http://arxiv.org/abs/1308.6444 ).     

Circulant Double Coverings of a Circulant Graph of Valency Four

Several isomorphism classes of graph coverings of a graph G have been enumerated by many authors (see [3], [8]–[15]). A covering of G is called circulant if its covering graph is circulant. Recently, the authors [4] enumerated the isomorphism classes of circulant double coverings of a certain kind, called typical, and showed that no double covering of a circulant graph of valency 3 is circulant. In this paper, the isomorphism classes of connected circulant double coverings of a circulant graph of valency 4 are enumerated. As a consequence, it is shown that no double covering of a non-circulant graph G of valency 4 can be circulant if G is vertex-transitive or G has a prime power of vertices. The first author is supported by NSF of China (No. 60473019) and by NKBRPC (2004CB318000), and the second author is supported by Com²MaC-KOSEF (R11-1999-054) in Korea.