Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problem

arXiv0812.1278MaRDI QIDQ6211871FDOQ6211871

Hamza Si Kaddour, Maurice Pouzet

Publication date: 6 December 2008

Abstract: We describe $Forb{K}_{1,3},overline{K}_{1,3}$, the class of graphs $G$ such that $G$ and its complement $overlineG$ are claw-free. With few exceptions, it is made of graphs whose connected components consist of cycles of length at least 4, paths or isolated vertices, and of the complements of these graphs. Considering the hypergraph ${mathcalH}^{(3)}(G)$ made of the 3-element subsets of the vertex set of a graph $G$ on which $G$ induces a clique or an independent subset, we deduce from above a description of the Boolean sum $Gdot+G^{\prime }$ of two graphs $G$ and $G^{\prime }$ giving the same hypergraph. We indicate the role of this latter description in a reconstruction problem of graphs up to complementation.

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

This page was built for publication: Claw-freeness, 3-homogeneous subsets of a graph and a reconstruction problem

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