The enumeration of self-complementary k-multigraphs

DOI10.1007/BF02679899MaRDI QIDQ1582580zbMATH OpenFDO

Authors Jin Xu

Publication date 28 May 2001

Published in Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF02679899

zbMATH Keywords

enumeration up to isomorphismself-complementary \(k\)-multigraphs

Mathematics Subject Classification ID

Enumeration in graph theory (05C30)

Review text

In a \(k\)-multigraph \(G\), any pair of vertices can be joined by at most \(k\) edges. If every pair of vertices joined by \(i\) edges are instead joined by \(k-i\) edges, then \(G\) is transformed into its complement \(\overline G\). If \(G\) is isomorphic to \(\overline G\), then \(G\) is self-complementary. The paper under review uses Pólya theory to obtain a formula for the number of non-isomorphic self-complementary \(k\)-multigraphs with \(p\) vertices. This result generalizes to \(k\)-multigraphs an analogous result for graphs in \textit{R. C. Read} [J. Lond. Math. Soc. 38, 99-104 (1963; Zbl 0116.15001)].

Recommendations

• Self-complementary 2-multigraphs. I: Degree sequences
• Some results on generalized self-complementary graphs
• Complement of a graph: a generalization
• Graphs that accept forced relative self-complementation
• On cyclically \(K\)-complementary graphs

Cites work

• A class of self-complementary vertex-transitive digraphs
• Characterisation of potentially bipartite self-complementary bipartitioned sequences
• Chromaticity of self-complementary graphs
• scientific article; zbMATH DE number 3708283 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• scientific article; zbMATH DE number 3419161 (Why is no real title available?)
• scientific article; zbMATH DE number 3194323 (Why is no real title available?)
• On regular and strongly-regular self-complementary graphs
• On self-complementary strongly regular graphs
• On the Number of Self-Complementary Graphs and Digraphs
• Selbstkomplementäre Graphen
• Self-complementary graphs
• Self-complementary graphs and Ramsey numbers. I: The decomposition and construction of self-complementary graphs
• The chromatic polynomial between graph \& its complement---about Akiyama and Harary's open problem
• The degree sequences of self-complementary graphs
• The Number of Linear, Directed, Rooted, and Connected Graphs

Cited in

(1)

• A new counting methods, including the issue of counting labelled self-complementary graphs

This page was built for publication: The enumeration of self-complementary \(k\)-multigraphs

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