On the structure of self-complementary graphs

DOI10.1016/J.ENDM.2005.06.014MaRDI QIDQ3439312zbMATH OpenOpenAlexFDO

Authors Nicolas Trotignon

Publication date 29 May 2007

Published in Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

decompositiongraphself-complementary

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Abstract: A emph{self-complementary} graph is a graph isomorphic to its complement. An isomorphism between $G$ and its complement, viewed as a permutation of $V(G)$, is then called an emph{antimorphism}. A emph{skew partition} of $G$ is a partition of $V(G)$ into 4 sets $A,B,C,D$ such that there is no edge between $A,B$ and every possible edge between $C,D$. A emph{symmetric partition} of $G$ is a partition of $V(G)$ into 4 sets $A,B,C,D$ such that there is no edge between $A,D$, no edge between $B,C$, every possible edge between $A,B$ and every possible edge between $C,D$. We give a new proof of a theorem of Gibbs saying that every self-complementary graph on $4k$ vertices has $k$ disjoint paths on 4 vertices as induced subgraph. This new proof gives more structural information than the original one. We conjecture that every self-complementary graph on $4k$ vertices either has an induced cycle on 5 vertices, or a skew partition, or a symmetric partition. The new proof of Gibb's theorem yields a proof of the conjecture for the self-complementary graphs that have an antimorphism that is the product of a two circular permutations, one of them of length 4.

Cites work

• Berge trigraphs
• Complexity of graph partition problems
• Compositions for perfect graphs
• FindingH-partitions efficiently
• scientific article; zbMATH DE number 3604941 (Why is no real title available?)
• scientific article; zbMATH DE number 1545651 (Why is no real title available?)
• scientific article; zbMATH DE number 3194323 (Why is no real title available?)
• On the completeness of a generalized matching problem
• Selbstkomplementäre Graphen
• Self-complementary graphs
• Star-cutsets and perfect graphs
• The strong perfect graph theorem

Cited in

(1)

• Coefficients of the matching polynomial of a self-complementary graph

This page was built for publication: On the structure of self-complementary graphs

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