Clique-perfectness of complements of line graphs

The clique-transversal number τ_c(G) of a graph G is the minimum size of a set of vertices meeting all the cliques. The clique-independence number α_c(G) of G is the maximum size of a collection of vertex-disjoint cliques. A graph is clique-perfect if these two numbers are equal for every induced subgraph of G. Unlike perfect graphs, the class of clique-perfect graphs is not closed under graph complementation nor is a characterization by forbidden induced subgraphs known. Nevertheless, partial results in this direction have been obtained. For instance, in [Bonomo, F., M. Chudnovsky and G. Durán, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, Discrete Appl. Math. 156 (2008), pp. 1058–1082], a characterization of those line graphs that are clique-perfect is given in terms of minimal forbidden induced subgraphs. Our main result is a characterization of those complements of line graphs that are clique-perfect, also by means of minimal forbidden induced subgraphs. This implies an O(n²) time algorithm for deciding the clique-perfectness of complements of line graphs and, for those that are clique-perfect, finding α_c and τ_c.     

A Classification of the Strongly Regular Generalised Johnson Graphs

The generalised Johnson graphs are the graphs J(n, k, m) whose vertices are the k subsets of {1, 2, . . . , n}, with two vertices J ₁ and J ₂ joined by an edge if and only if ${{|J_1 \cap J_2| = m}}$ . A graph is called d-regular if every vertex has exactly d edges incident to it. A d-regular graph on v vertices is called a (v, d, a, c)-strongly regular graph if every pair of adjacent vertices have exactly a common neighbours and every pair of non-adjacent vertices have exactly c common neighbours. The triangular graphs J(n, 2, 1), their complements J(n, 2, 0), the sporadic examples J(10, 3, 1) and J(7, 3, 1), as well as the trivially strongly regular graphs J(2k, k, 0) are examples of strongly regular generalised Johnson graphs. In this paper we prove that there are no other strongly regular generalised Johnson graphs.     

Interval <Emphasis Type="Italic">k</Emphasis>-Graphs and Orders

An interval k-graph is the intersection graph of a family of intervals of the real line partitioned into k classes with vertices adjacent if and only if their corresponding intervals intersect and belong to different classes. In this paper we study the cocomparability interval k-graphs; that is, the interval k-graphs whose complements have a transitive orientation and are therefore the incomparability graphs of strict partial orders. For brevity we call these orders interval k-orders. We characterize the kind of interval representations a cocomparability interval k-graph must have, and identify the structure that guarantees an order is an interval k-order. The case k =?2 is peculiar: cocomparability interval 2-graphs (equivalently proper- or unit-interval bigraphs, bipartite permutation graphs, and complements of proper circular-arc graphs to name a few) have been characterized in many ways, but we show that analogous characterizations do not hold if k >?2. We characterize the cocomparability interval 3-graphs via one forbidden subgraph and hence interval 3-orders via one forbidden suborder.     

Planar segment visibility graphs

Given a set of n disjoint line segments in the plane, the segment visibility graph is the graph whose 2n vertices correspond to the endpoints of the line segments and whose edges connect every pair of vertices whose corresponding endpoints can see each other. In this paper we characterize and provide a polynomial time recognition algorithm for planar segment visibility graphs. Actually, we characterize segment visibility graphs that do not contain the complete graph K₅ as a minor, and show that this class is the same as the class of planar segment visibility graphs. We use and prove the fact that every segment visibility graph contains K₄ as a subgraph. In fact, we prove a stronger result: every set of n line segments determines at least n−3 empty convex quadrilaterals.     

Every 4-Connected Line Graph of a Planar Graph is Hamiltonian

Let G be a graph withE(G) $#x2260;ø. The line graph of G, written L(G) hasE(G) as its vertex set, where two vertices are adjacent in L(G) if and only if the corresponding edges are adjacent inG. Thomassen conjectured that all 4-connected line graphs are hamiltonian [2]. We show that this conjecture holds for planar graphs.     

A spectral characterization of the line graph of a BIBD with λ=1

The line graph of a balanced incomplete block design has as its vertices the ordered pairs (v, B), where B is a block and v is a variety contained in that block. Two vertices are adjacent if they agree in one coordinate Since the line graphs are isomorphic only when the designs are isomorphic, various characterizations of the line graph of a BIBD have been given. The following is proved herein: A BIBD with λ=1 is characterized by its spectrum if r+k>18.     

On minimal forbidden subgraph characterizations of balanced graphs

A graph is balanced if its clique-matrix contains no edge–vertex incidence matrix of an odd chordless cycle as a submatrix. While a forbidden induced subgraph characterization of balanced graphs is known, there is no such characterization by minimal forbidden induced subgraphs. In this work, we provide minimal forbidden induced subgraph characterizations of balanced graphs restricted to graphs that belong to one of the following graph classes: complements of bipartite graphs, line graphs of multigraphs, and complements of line graphs of multigraphs. These characterizations lead to linear-time recognition algorithms for balanced graphs within the same three graph classes.     

On the Connectivity of Visibility Graphs

The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesník (Acta Fac. Rerum Nat. Univ. Comen. Math. 30:71?C93, 1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesník by showing that for any two vertices v and w in a graph of diameter 2, if deg(v)??deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. For vertex-connectivity, we prove that every visibility graph with n vertices and at most ? collinear vertices has connectivity at least $\frac{n-1}{\ell-1}$ , which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, in the case that ?=4 we improve this bound to two thirds of the minimum degree.     

Classes of graphs with minimum skew rank 4

The minimum skew rank of a simple graph G   is the smallest possible rank among all real skew-symmetric matrices whose (i,j)$(i,j)$-entry is nonzero if and only if the edge joining i and j is in G. It is known that a graph has minimum skew rank 2 if and only if it consists of a complete multipartite graph and some isolated vertices. Some necessary conditions for a graph to have minimum skew rank 4 are established, and several families of graphs with minimum skew rank 4 are given. Linear algebraic techniques are developed to show that complements of trees and certain outerplanar graphs have minimum skew rank 4.     

Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs

Equistable graphs are graphs admitting positive weights on vertices such that a subset of vertices is a maximal stable set if and only if it is of total weight 1. Strongly equistable graphs are graphs such that for every and every nonempty subset T of vertices that is not a maximal stable set, there exist positive vertex weights assigning weight 1 to every maximal stable set such that the total weight of T does not equal c . General partition graphs are the intersection graphs of set systems over a finite ground set U such that every maximal stable set of the graph corresponds to a partition of U . General partition graphs are exactly the graphs every edge of which is contained in a strong clique. In 1994, Mahadev, Peled, and Sun proved that every strongly equistable graph is equistable, and conjectured that the converse holds as well. In 2009, Orlin proved that every general partition graph is equistable, and conjectured that the converse holds as well. Orlin's conjecture, if true, would imply the conjecture due to Mahadev, Peled, and Sun. An “intermediate” conjecture, posed by Miklavi? and Milani? in 2011, states that every equistable graph has a strong clique. The above conjectures have been verified for several graph classes. We introduce the notion of equistarable graphs and based on it construct counterexamples to all three conjectures within the class of complements of line graphs of triangle‐free graphs. We also show that not all strongly equistable graphs are general partition.     

An algorithm to recognize a middle graph

A graph F is called middle if there exists a graph G such that there is a one-to-one correspondence between the vertices of F and the vertices and edges of G such that two vertices of F are adjacent if and only if the corresponding elements (considered as subsets of the set of vertices) have a non-empty intersection.In this paper we present a linear time algorithm for the recognition of the middle graphs. The algorithm is based on a computer-oriented characterization of middle graphs. We show also how the algorithm can be generalized to recognize the middle graphs of hypergraphs.     

Triangular line graphs and word sense disambiguation

Linguists often represent the relationships between words in a collection of text as an undirected graph G=(V,E), where V is the vocabulary and vertices are adjacent in G if and only if the words that they represent co-occur in a relevant pattern in the text. Ideally, the words with similar meanings give rise to the vertices of a component of the graph. However, many words have several distinct meanings, preventing components from characterizing distinct semantic fields. This paper examines how the structural properties of triangular line graphs motivate the use of a clustering coefficient on the triangular line graph, thereby helping to identify polysemous words. The triangular line graph of G, denoted by T(G), is the subgraph of the line graph of G where two vertices are adjacent if the corresponding edges in G belong to a K₃.     

Graphs with intrinsic s3 convexities

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

On a conjecture of Brouwer involving the connectivity of strongly regular graphs

In this paper, we study a conjecture of Andries E. Brouwer from 1996 regarding the minimum number of vertices of a strongly regular graph whose removal disconnects the graph into non-singleton components.We show that strongly regular graphs constructed from copolar spaces and from the more general spaces called Δ-spaces are counterexamples to Brouwer?s Conjecture. Using J.I. Hall?s characterization of finite reduced copolar spaces, we find that the triangular graphs T(m), the symplectic graphs Sp(2r,q) over the field Fq (for any q prime power), and the strongly regular graphs constructed from the hyperbolic quadrics O⁺(2r,2) and from the elliptic quadrics O⁻(2r,2) over the field F₂, respectively, are counterexamples to Brouwer?s Conjecture. For each of these graphs, we determine precisely the minimum number of vertices whose removal disconnects the graph into non-singleton components. While we are not aware of an analogue of Hall?s characterization theorem for Δ-spaces, we show that complements of the point graphs of certain finite generalized quadrangles are point graphs of Δ-spaces and thus, yield other counterexamples to Brouwer?s Conjecture.We prove that Brouwer?s Conjecture is true for many families of strongly regular graphs including the conference graphs, the generalized quadrangles GQ(q,q) graphs, the lattice graphs, the Latin square graphs, the strongly regular graphs with smallest eigenvalue −2 (except the triangular graphs) and the primitive strongly regular graphs with at most 30 vertices except for few cases.We leave as an open problem determining the best general lower bound for the minimum size of a disconnecting set of vertices of a strongly regular graph, whose removal disconnects the graph into non-singleton components.     

The superregular graphs

A regular graph is superregular if it has no vertices or if the subgraphs induced by the neighbors and by the nonneighbors of each vertex are superregular. The superregular graphs are precisely the disjoint union of m isomorphic cliques, the Cartesian product of two isomorphic cliques, the five-cycle, and the complements of these graphs. © 1996 John Wiley & Sons, Inc.     

Planar unit-distance graphs having planar unit-distance complement

A graph G=(V,E) is called a unit-distance graph in the plane if there is an embedding of V into the plane such that every pair of adjacent vertices are at unit distance apart. If an embedding of V satisfies the condition that two vertices are adjacent if and only if they are at unit distance apart, then G is called a strict unit-distance graph in the plane. A graph G is a (strict) co-unit-distance graph, if both G and its complement are (strict) unit-distance graphs in the plane. We show by an exhaustive enumeration that there are exactly 69 co-unit-distance graphs (65 are strict co-unit-distance graphs), 55 of which are connected (51 are connected strict co-unit-distance graphs), and seven are self-complementary.     

Super-connected edge transitive graphs

A graph G is said to be super-connected if any minimum cut of G isolates a vertex. In a previous work due to the second author of this note, super-connected graphs which are both vertex transitive and edge transitive are characterized. In this note, we generalize the characterization to edge transitive graphs which are not necessarily vertex transitive, showing that the only irreducible edge transitive graphs which are not super-connected are the cycles C_n(n?6) and the line graph of the 3-cube, where irreducible means the graph has no vertices with the same neighbor set. Furthermore, we give some sufficient conditions for reducible edge transitive graphs to be super-connected.     

Graphs with three mutually pseudo-similar vertices

Vertices u and v of a graph X are pseudo-similar if X ? u ? X ? v but no automorphism of X maps u to v. We describe a group-theoretic method for constructing graphs with a set of three mutually pseudo-similar vertices. The method is used to construct several examples of such graphs. An algorithm for extending, in a natural way, certain graphs with three mutually pseudo-similar vertices to a graph in which the three vertices are similar is given. The algorithm suggests that no simple characterization of graphs with a set of three mutually pseudo-similar vertices can exist.     

Special Eccentric Vertices for the Class of Chordal Graphs and Related Classes

A vertex is simplicial if the vertices of its neighborhood are pairwise adjacent. It is known that, for every vertex v of a chordal graph, there exists a simplicial vertex among the vertices at maximum distance from v. Here we prove similar properties in other classes of graphs related to that of chordal graphs. Those properties will not be in terms of simplicial vertices, but in terms of other types of vertices that are used to characterize those classes.     

Graphs with a Minimal Number of Convex Sets

Let G be a graph with vertex set V(G). A set C of vertices of G is g-convex if for every pair \({u, v \in C}\) the vertices on every u–v geodesic (i.e. shortest u–v path) belong to C. If the only g-convex sets of G are the empty set, V(G), all singletons and all edges, then G is called a g-minimal graph. It is shown that a graph is g-minimal if and only if it is triangle-free and if it has the property that the convex hull of every pair of non-adjacent vertices is V(G). Several properties of g-minimal graphs are established and it is shown that every triangle-free graph is an induced subgraph of a g-minimal graph. Recursive constructions of g-minimal graphs are described and bounds for the number of edges in these graphs are given. It is shown that the roots of the generating polynomials of the number of g-convex sets of each size of a g-minimal graphs are bounded, in contrast to their behaviour over all graphs. A set C of vertices of a graph is m-convex if for every pair \({u, v \in C}\) , the vertices of every induced u–v path belong to C. A graph is m-minimal if it has no m-convex sets other than the empty set, the singletons, the edges and the entire vertex set. Sharp bounds on the number of edges in these graphs are given and graphs that are m-minimal are shown to be precisely the 2-connected, triangle-free graphs for which no pair of adjacent vertices forms a vertex cut-set.