DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

P. Rowlinson

Title:

On trees as star complements in regular graphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-02-04, Revised: 2019-08-07, Accepted: 2019-08-08, https://doi.org/10.7151/dmgt.2272

Abstract:

Let $G$ be a connected $r$-regular graph $(r  >  3)$ of order $n$ with a tree of order $t$ as a star complement for an eigenvalue {$\mu\not\in\{-1,0\}$.} It is shown that $n\le \frac12 (r+1)t-2$. Equality holds when $G$ is the complement of the Clebsch graph (with $\mu=1$, $r=5$, $t=6$, $n=16$).

Keywords:

eigenvalue, regular graph, star complement, tree

PDF
Close