Journal Article

·2015 OPEN ACCESS

A complete solution to the spectrum problem for graphs with six vertices and up to nine edges

Emre Kolotoğlu YTU

Contributions to Discrete Mathematics

Abstract

Let $G$ be a graph. A $G$-design of order $n$ is a decomposition of the complete graph $K_n$ into disjoint copies of $G$. The existence problem of graph designs has been completely solved for all graphs with up to five vertices, and all graphs with six vertices and up to seven edges; and almost completely solved for all graphs with six vertices and eight edges leaving two cases of order 32 unsettled. Up to isomorphism there are 20 graphs with six vertices and nine edges (and no isolated vertex). The spectrum problem has been solved completely for 11 of these graphs, and partially for 2 of these graphs. In this article, the two missing graph designs for the six-vertex eight-edge graphs are constructed, and a complete solution to the spectrum problem for the six-vertex nine-edge graphs is given; completing the spectrum problem for all graphs with six vertices and up to nine edges.

Keywords

Combinatorics Mathematics Cograph 1-planar graph Indifference graph Chordal graph Pathwidth Metric dimension Vertex (graph theory) Discrete mathematics Neighbourhood (mathematics) Clique-sum Graph Line graph

Subject Areas

graph theory and CDMA systems ·Electrical and Electronic Engineering ·Physical Sciences
Nuclear Receptors and Signaling ·Cellular and Molecular Neuroscience ·Life Sciences
Finite Group Theory Research ·Discrete Mathematics and Combinatorics ·Physical Sciences