Clique-partitioned graphs

DOI10.1016/J.DAM.2022.02.024MaRDI QIDQ2127629zbMATH OpenOpenAlexFDO

Authors Grahame Erskine, T. S. Griggs, Jozef Širáň

Publication date 20 April 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

cliquesextremal graphspartition

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: A graph $G$ of order $nv$ where $ngeq2$ and $vgeq2$ is said to be weakly $(n,v)$-clique-partitioned if its vertex set can be decomposed in a unique way into $n$ vertex-disjoint $v$-cliques. It is strongly $(n,v)$-clique-partitioned if in addition, the only $v$-cliques of $G$ are the $n$ cliques in the decomposition. We determine the structure of such graphs which have the largest possible number of edges.

Recommendations

• scientific article; zbMATH DE number 3885943
• scientific article; zbMATH DE number 3914369
• Maximal-clique partitions of different sizes.
• Graph partition into small cliques
• Clique Partitions of Chordal Graphs

Cites work

• Graph theory applications
• scientific article; zbMATH DE number 3977022 (Why is no real title available?)
• scientific article; zbMATH DE number 1232919 (Why is no real title available?)
• scientific article; zbMATH DE number 3041944 (Why is no real title available?)
• On the structure of factorizable graphs
• On the theory of graphs
• Uniquely colorable Cayley graphs
• Uniqueness of colorings

Cited in

(6)

• Clique-gated graphs
• Graphs vertex-partitionable into strong cliques
• scientific article; zbMATH DE number 1750103 (Why is no real title available?)
• scientific article; zbMATH DE number 3999981 (Why is no real title available?)
• On the partition and coloring of a graph by cliques
• Graph partition into small cliques

Describes a project that uses

Uses Software

• GRAPE
• GAP

This page was built for publication: Clique-partitioned graphs

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