Journal Article

·2020 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 Pathwidth Indifference graph Chordal graph Metric dimension Discrete mathematics Vertex (graph theory) Clique-sum Neighbourhood (mathematics) Graph Line graph

Subject Areas

graph theory and CDMA systems ·Electrical and Electronic Engineering ·Physical Sciences
Optimal Experimental Design Methods ·Management Science and Operations Research ·Social Sciences

Citations by Year