Spectral characterization of mixed extensions of small graphs

Research output: Contribution to journalArticleScientificpeer-review

Abstract

A mixed extension of a graph $G$ is a graph $H$ obtained from $G$ by replacing each vertex of $G$ by a clique or a coclique, where vertices of $H$ coming from different vertices of $G$ are adjacent if and only if the original vertices are adjacent in $G$. If $G$ has no more than three vertices, $H$ has all but at most three adjacency eigenvalues equal to $0$ or $-1$. In this paper we consider the converse problem, and determine the class $\cal G$ of all graphs with at most three eigenvalues unequal to $0$ and $-1$. Ignoring isolated vertices, we find that $\cal G$ consists of all mixed extensions of graphs on at most three vertices together with some particular mixed extensions of the paths $P_4$ and $P_5$.
Original languageEnglish
JournalDiscrete Mathematics
DOIs
Publication statusE-pub ahead of print - Feb 2018

Fingerprint

Graph in graph theory
Adjacent
Eigenvalue
Adjacency
Unequal
Clique
Converse
If and only if
Path
Vertex of a graph
Class

Keywords

  • graph spectrum
  • spectral characterization

Cite this

@article{2f26b273db434a87930f1f56882c383e,
title = "Spectral characterization of mixed extensions of small graphs",
abstract = "A mixed extension of a graph $G$ is a graph $H$ obtained from $G$ by replacing each vertex of $G$ by a clique or a coclique, where vertices of $H$ coming from different vertices of $G$ are adjacent if and only if the original vertices are adjacent in $G$. If $G$ has no more than three vertices, $H$ has all but at most three adjacency eigenvalues equal to $0$ or $-1$. In this paper we consider the converse problem, and determine the class $\cal G$ of all graphs with at most three eigenvalues unequal to $0$ and $-1$. Ignoring isolated vertices, we find that $\cal G$ consists of all mixed extensions of graphs on at most three vertices together with some particular mixed extensions of the paths $P_4$ and $P_5$.",
keywords = "graph spectrum, spectral characterization",
author = "Haemers, {Willem H.}",
year = "2018",
month = "2",
doi = "10.1016/j.disc.2018.02.005",
language = "English",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",

}

Spectral characterization of mixed extensions of small graphs. / Haemers, Willem H.

In: Discrete Mathematics, 02.2018.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Spectral characterization of mixed extensions of small graphs

AU - Haemers, Willem H.

PY - 2018/2

Y1 - 2018/2

N2 - A mixed extension of a graph $G$ is a graph $H$ obtained from $G$ by replacing each vertex of $G$ by a clique or a coclique, where vertices of $H$ coming from different vertices of $G$ are adjacent if and only if the original vertices are adjacent in $G$. If $G$ has no more than three vertices, $H$ has all but at most three adjacency eigenvalues equal to $0$ or $-1$. In this paper we consider the converse problem, and determine the class $\cal G$ of all graphs with at most three eigenvalues unequal to $0$ and $-1$. Ignoring isolated vertices, we find that $\cal G$ consists of all mixed extensions of graphs on at most three vertices together with some particular mixed extensions of the paths $P_4$ and $P_5$.

AB - A mixed extension of a graph $G$ is a graph $H$ obtained from $G$ by replacing each vertex of $G$ by a clique or a coclique, where vertices of $H$ coming from different vertices of $G$ are adjacent if and only if the original vertices are adjacent in $G$. If $G$ has no more than three vertices, $H$ has all but at most three adjacency eigenvalues equal to $0$ or $-1$. In this paper we consider the converse problem, and determine the class $\cal G$ of all graphs with at most three eigenvalues unequal to $0$ and $-1$. Ignoring isolated vertices, we find that $\cal G$ consists of all mixed extensions of graphs on at most three vertices together with some particular mixed extensions of the paths $P_4$ and $P_5$.

KW - graph spectrum

KW - spectral characterization

U2 - 10.1016/j.disc.2018.02.005

DO - 10.1016/j.disc.2018.02.005

M3 - Article

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

ER -