Minimizing algebraic connectivity over connected graphs with fixed girth (Q1613533): Difference between revisions
From MaRDI portal
Created a new Item |
Set OpenAlex properties. |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/s0012-365x(01)00355-7 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W1996070164 / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 10:50, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Minimizing algebraic connectivity over connected graphs with fixed girth |
scientific article |
Statements
Minimizing algebraic connectivity over connected graphs with fixed girth (English)
0 references
29 August 2002
0 references
Let \(G_{n,g}\) denote the class of all connected graphs with \(n\) vertices and girth \(g\), and let \(C_{n,g}\) denote the unicyclic ``lollipop'' graph obtained by joining with an edge a vertex of a \(g\)-cycle and a pendant vertex of a path on \(n-g\) vertices. Two of the present authors have earlier conjectured that \(C_{n,g}\) is the unique graph minimizing the algebraic connectivity over \(G_{n,g}\) and confirmed this conjecture for \(g=3\) (see \textit{S. Fallat} and \textit{S. Kirkland} [Electron. J. Linear Algebra 3, 48-74 (1998; Zbl 0913.05073)]). Resuming the results of the previous paper, the authors here confirm the conjecture for the case \(n\geq 3g-1\), as well as for the case \(g=4\). Further, for each fixed \(g\geq 5\) and \(n<3g-1\), they describe the class, containing less than \({n-g\choose g}\) graphs, for which the conjecture could be verified numerically using a standard mathematical package. Besides this, the authors also discuss the characteristic set of the graphs \(C_{n,g}\).
0 references
Laplacian matrix
0 references
algebraic connectivity
0 references
girth
0 references
unicyclic graph
0 references
characteristic set
0 references