Intersection graph of maximal stars
share
A biclique of a graph G is an induced complete bipartite subgraph of G such that neither part is empty. A star is a biclique of G such that one part has exactly one vertex. The star graph of G is the intersection graph of the maximal stars of G. A graph H is star-critical if its star graph is different from the star graph of any of its proper induced subgraphs. We begin by presenting a bound on the size of star-critical pre-images by a quadratic function on the number of vertices of the star graph, then proceed to describe a Krausz-type characterization for this graph class; we combine these results to show membership of the recognition problem in NP. We also present some properties of star graphs. In particular, we show that they are biconnected, that every edge belongs to at least one triangle, characterize the structures the pre-image must have in order to generate degree two vertices, and bound the diameter of the star graph with respect to the diameter of its pre-image. Finally, we prove a monotonicity theorem, which we apply to list every star graph on at most eight vertices.
READ FULL TEXT