Intersection graph of maximal stars

DOI10.1016/J.DAM.2020.07.004MaRDI QIDQ2197473zbMATH OpenOpenAlexFDO

Authors Guilherme de C. M. Gomes, Vinícius F. dos Santos, Marina Groshaus, Carlos Vinícius G. C. Lima

Publication date 31 August 2020

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1911.10515

zbMATH Keywords

intersection graphsstarsstar graphscliquesedge clique covers

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph operations (line graphs, products, etc.) (05C76)

Abstract: 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 extsf{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.

Recommendations

• Characterizing intersection graphs of substars of a star.
• On star and biclique edge-colorings
• A characterization of substar graphs
• The Star and Biclique Coloring and Choosability Problems
• scientific article; zbMATH DE number 22640

Cites work

• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• A characterization of clique graphs
• A characterization of substar graphs
• Almost every graph is divergent under the biclique operator
• An efficient reconstruction of a graph from its line graph in parallel
• Biclique graphs and biclique matrices
• Characterizing intersection graphs of substars of a star.
• Clique-critical graphs: maximum size and recognition
• Dismantlings and iterated clique graphs
• Graph Classes: A Survey
• Graph theory with applications
• On clique divergent graphs with linear growth
• On clique-critical graphs
• On cliques in graphs
• On the iterated biclique operator
• On the iterated edge-biclique operator
• Practical graph isomorphism. II.
• The Star and Biclique Coloring and Choosability Problems
• The complexity of clique graph recognition
• Traces

Cited in

(5)

• A characterization of substar graphs
• Crossing Stars in Topological Graphs
• Representing triangulated graphs in stars
• Characterizing intersection graphs of substars of a star.
• Bipartite graphs without a skew star

Describes a project that uses

Uses Software

• Traces
• nauty

This page was built for publication: Intersection graph of maximal stars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2197473)