全部 标题 作者
关键词 摘要

OALib Journal期刊
ISSN: 2333-9721
费用:99美元

查看量下载量

相关文章

更多...

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

Full-Text   Cite this paper   Add to My Lib

Abstract:

We describe $Forb{K_{1,3}, overline {K_{1,3}}}$, the class of graphs $G$ such that $G$ and its complement $ overline{G}$ 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 ${mathcal H} ^{(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'$ of two graphs $G$ and $G'$ giving the same hypergraph. We indicate the role of this latter description in a reconstruction problem of graphs up to complementation.

Full-Text

Contact Us

service@oalib.com

QQ:3279437679

WhatsApp +8615387084133