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.     

Distance-regular graphs of large diameter that are completely regular clique graphs

A connected graph is said to be a completely regular clique graph with parameters (s, c), \(s, c \in {\mathbb {N}}\), 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}\). It is known that many families of distance-regular graphs are completely regular clique graphs. In this paper, we determine completely regular clique graph structures, i.e., the choices of \(\mathcal {C}\), of all known families of distance-regular graphs with unbounded diameter. In particular, we show that all distance-regular graphs in this category are completely regular clique graphs except the Doob graphs, the twisted Grassmann graphs and the Hermitean forms graphs. We also determine parameters (s, c); however, in a few cases we determine only s and give a bound on the value c. Our result is a generalization of a series of works by J. Hemmeter and others who determined distance-regular graphs in this category that are bipartite halves of bipartite distance-regular 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.     

The clique numbers of regular graphs of matrix algebras are finite

Let F be a field, char(F)≠2, and SGL_n(F), where n is a positive integer. In this paper we show that if for every distinct elements x,yS, x+y is singular, then S is finite. We conjecture that this result is true if one replaces field with a division ring.     

Squares,clique graphs,and chordality

We study the squares and the clique graphs of chordal graphs and various special classes of chordal graphs. Chordality conditions for squares and clique graphs are given. Several theorems concering chordal graphs are generalized. © 1996 John Wiley & Sons, Inc.     

Vertex-magic labelings of regular graphs II

Previously the first author has shown how to construct vertex-magic total labelings (VMTLs) for large families of regular graphs. The construction proceeds by successively adding arbitrary 2-factors to a regular graph of order n which possesses a strong VMTL, to produce a regular graph of the same order but larger size. In this paper, we exploit this construction method. We are able to show that for any r≥4, every r-regular graph of odd order n≤17 has a strong VMTL. We show how to produce strong labelings for some families of 2-regular graphs since these are used as the starting points of our construction. While even-order regular graphs are much harder to deal with, we introduce ‘mirror’ labelings which provide a suitable starting point from which the construction can proceed. We are able to show that several large classes of r-regular graphs of even order (including some Hamiltonian graphs) have VMTLs.     

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.     

On joins of a clique and a co-clique as star complements in regular graphs

Journal of Algebraic Combinatorics - In this paper we consider r-regular graphs G that admit the vertex set partition such that one of the induced subgraphs is the join of an s-vertex clique and a...     

Completely regular designs

We study a class of t-designs which enjoy a high degree of regularity. These are the subsets of vertices of the Johnson graph which are completely regular, in the sense of Delsarte [Philips Res. Reports Suppl. 10 (1973)]. After setting up the basic theory, we describe the known completely regular designs. We derive very strong restrictions which must hold in order for a design to be completely regular. As a result, we are able to determine which symmetric designs are completely regular and which Steiner systems with t = 2 are completely regular. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 261–273, 1998     

Completely regular semigroups

No abstract. August 22, 2001     

Algorithms on clique separable graphs

We define a family of graphs, called the clique separable graphs, characterized by the fact that they have completely connected cut sets by which we decompose them into parts such that when no further decomposition is possible we have a set of simple subgraphs. For example the chordal graphs and the i-triangulated graphs are clique separable graphs.The purpose of this paper is to describe polynomial time algorithms for the recognition of the clique separable graphs and for finding them a minimum coloring and a maximum clique.     

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.     

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.     

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.     

Completely regular ordered spaces

We present an example of a completely regular ordered space that is not strictly completely regular ordered. Furthermore, we note that a completely regular ordered I-space is strictly completely regular ordered provided that it satisfies at least one of the following three conditions: It is locally compact, it is a C-space, it is a topological lattice.     

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?