A note on a conjecture by Gavril on clique separable graphs

In this note we disprove Gavril's conjecture concerning the characterization of clique separable graphs.     

Completely regular clique graphs

Let Γ=(X,R) be a connected graph. Then Γ is said to be a completely regular clique graph of parameters (s,c) with s≥1 and c≥1, if there is a collection \(\mathcal{C}\) of completely regular cliques of size s+1 such that every edge is contained in exactly c members of  \(\mathcal{C}\) . In this paper, we show that the parameters of \(C\in\mathcal{C}\) as a completely regular code do not depend on \(C\in\mathcal{C}\) . As a by-product we have that all completely regular clique graphs are distance-regular whenever \(\mathcal {C}\) consists of edges. We investigate the case when Γ is distance-regular, and show that Γ is a completely regular clique graph if and only if it is a bipartite half of a distance-semiregular graph.     

The clique operator on circular-arc graphs

A circular-arc graphG is the intersection graph of a collection of arcs on the circle and such a collection is called a model of G. Say that the model is proper when no arc of the collection contains another one, it is Helly when the arcs satisfy the Helly Property, while the model is proper Helly when it is simultaneously proper and Helly. A graph admitting a Helly (resp. proper Helly) model is called a Helly (resp. proper Helly) circular-arc graph. The clique graphK(G) of a graph G is the intersection graph of its cliques. The iterated clique graphKⁱ(G) of G is defined by K⁰(G)=G and Kⁱ⁺¹(G)=K(Kⁱ(G)). In this paper, we consider two problems on clique graphs of circular-arc graphs. The first is to characterize clique graphs of Helly circular-arc graphs and proper Helly circular-arc graphs. The second is to characterize the graph to which a general circular-arc graph K-converges, if it is K-convergent. We propose complete solutions to both problems, extending the partial results known so far. The methods lead to linear time recognition algorithms, for both problems.     

On clique convergent graphs

A graphG isconvergent when there is some finite integern 0, such that then-th iterated clique graphK ⁿ(G) has only one vertex. The smallest suchn is theindex ofG. TheHelly defect of a convergent graph is the smallestn such thatK ⁿ(G) is clique Helly, that is, its maximal cliques satisfy the Helly property. Bandelt and Prisner proved that the Helly defect of a chordal graph is at most one and asked whether there is a graph whose Helly defect exceeds the difference of its index and diameter by more than one. In the present paper an affirmative answer to the question is given. For any arbitrary finite integern, a graph is exhibited, the Helly defect of which exceeds byn the difference of its index and diameter.     

Algorithms for detecting optimal hereditary structures in graphs, with application to clique relaxations

Given a simple undirected graph, the problem of finding a maximum subset of vertices satisfying a nontrivial, interesting property Π that is hereditary on induced subgraphs, is known to be NP-hard. Many well-known graph properties meet the above conditions, making the problem widely applicable. This paper proposes a general purpose exact algorithmic framework to solve this problem and investigates key algorithm design and implementation issues that are helpful in tailoring the general framework for specific graph properties. The performance of the algorithms so derived for the maximum s-plex and the maximum s-defective clique problems, which arise in network-based data mining applications, is assessed through a computational study.     

Diameters of iterated clique graphs of chordal graphs

The clique graph K(G) of a graph is the intersection graph of maximal cliques of G. The iterated clique graph Kⁿ(G) is inductively defined as K(K^n?1(G)) and K¹(G) = K(G). Let the diameter diam(G) be the greatest distance between all pairs of vertices of G. We show that diam(Kⁿ(G)) = diam(G) — n if G is a connected chordal graph and n ≤ diam(G). This generalizes a similar result for time graphs by Bruce Hedman.     

Recognizing Helly Edge-Path-Tree graphs and their clique graphs

We present a unifying procedure for recognizing intersection graphs of Helly families of paths in a tree and their clique graphs. The Helly property makes it possible to look at these recognition problems as variants of the Graph Realization Problem, namely, the problem of recognizing Edge-Path-Tree matrices. Our result heavily relies on the notion of pie introduced in [M.C. Golumbic, R.E. Jamison, The edge intersection graphs of paths in a tree, Journal of Combinatorial Theory, Series B 38 (1985) 8-22] and on the observation that Helly Edge-Path-Tree matrices form a self-dual class of Helly matrices. Coupled to the notion of reduction presented in the paper, these facts are also exploited to reprove and slightly refine some known results for Edge-Path-Tree graphs.     

Competition graphs and clique dimensions

Here it is proved that for almost all simple graphs over n vertices one needs Ω(n^4/3(log n)^?4/3) extra vertices to obtain them as a double competition graph of a digraph. on the other hand O(n^5/3) extra vertices are always sufficient. Several problems remain open.     

On separable self-complementary graphs

In this paper, we describe the structure of separable self-complementary graphs.     

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?     

Edge clique cover of claw-free graphs

The smallest number of cliques, covering all edges of a graph , is called the (edge) clique cover number of and is denoted by . It is an easy observation that if is a line graph on vertices, then . G. Chen et al. [Discrete Math. 219 (2000), no. 1–3, 17–26; MR1761707] extended this observation to all quasi-line graphs and questioned if the same assertion holds for all claw-free graphs. In this paper, using the celebrated structure theorem of claw-free graphs due to Chudnovsky and Seymour, we give an affirmative answer to this question for all claw-free graphs with independence number at least three. In particular, we prove that if is a connected claw-free graph on vertices with three pairwise nonadjacent vertices, then and the equality holds if and only if is either the graph of icosahedron, or the complement of a graph on vertices called “twister” or the power of the cycle , for some positive integer .     

Sweeping graphs with large clique number

Searching a network for intruders is an interesting and often difficult problem. Sweeping (or edge searching) is one such search model, in which intruders may exist anywhere along an edge. It was conjectured that graphs exist for which the connected sweep number is strictly less than the monotonic connected sweep number. We prove that this is true, and the difference can be arbitrarily large. We also show that the clique number is a lower bound on the sweep number.     

The clique operator on matching and chessboard graphs

Given positive integers m,n, we consider the graphs G_n and G_m,n whose simplicial complexes of complete subgraphs are the well-known matching complex M_n and chessboard complex M_m,n. Those are the matching and chessboard graphs. We determine which matching and chessboard graphs are clique-Helly. If the parameters are small enough, we show that these graphs (even if not clique-Helly) are homotopy equivalent to their clique graphs. We determine the clique behavior of the chessboard graph G_m,n in terms of m and n, and show that G_m,n is clique-divergent if and only if it is not clique-Helly. We give partial results for the clique behavior of the matching graph G_n.     

Completely regular clique graphs,II

Let \(\varGamma = (X,R)\) be a connected graph. Then \(\varGamma \) is said to be a completely regular clique graph of parameters (s, c) with \(s\ge 1\) and \(c\ge 1\), if there is a collection \({\mathcal {C}}\) of completely regular cliques of size \(s+1\) such that every edge is contained in exactly c members of \({\mathcal {C}}\). In the previous paper (Suzuki in J Algebr Combin 40:233–244, 2014), we showed, among other things, that a completely regular clique graph is distance-regular if and only if it is a bipartite half of a certain distance-semiregular graph. In this paper, we show that a completely regular clique graph with respect to \({\mathcal {C}}\) is distance-regular if and only if every \({\mathcal {T}}(C)\)-module of endpoint zero is thin for all \(C\in {\mathcal {C}}\). We also discuss the relation between a \({\mathcal {T}}(C)\)-module of endpoint 0 and a \({\mathcal {T}}(x)\)-module of endpoint 1 and study examples of completely regular clique graphs.     

Iterated clique graphs with increasing diameters

A simple argument by Hedman shows that the diameter of a clique graph G differs by at most one from that of K(G), its clique graph. Hedman described examples of a graph G such that diam(K(G)) = diam(G) + 1 and asked in general about the existence of graphs such that diam(Kⁱ(G)) = diam(G) + i. Examples satisfying this equality for i = 2 have been described by Peyrat, Rall, and Slater and independently by Balakrishnan and Paulraja. The authors of the former work also solved the case i = 3 and i = 4 and conjectured that such graphs exist for every positive integer i. The cases i ≥ 5 remained open. In the present article, we prove their conjecture. For each positive integer i, we describe a family of graphs G such that diam(Kⁱ(G)) = diam(G) + i. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 147–154, 1998