On simply structured kernel bases of unicyclic graphs (Q2469301): Difference between revisions
From MaRDI portal
Created a new Item |
Added link to MaRDI item. |
||
links / mardi / name | links / mardi / name | ||
Revision as of 02:08, 3 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On simply structured kernel bases of unicyclic graphs |
scientific article |
Statements
On simply structured kernel bases of unicyclic graphs (English)
0 references
5 February 2008
0 references
This paper is dedicated to the study of unicyclic graphs for which there exists a simply structured kernel basis. Let \(G=(V,E)\) be a connected graph and \(A(G)\) its adjacency matrix. The authors refer to the kernel of the adjacency matrix of a graph as the kernel of the graph. A basis of a real vector space is called simply structured if it consists only of vectors with entries in \(\{-1,0,1 \}\). Of course, not every unicyclic graph has a simply structured kernel basis, but this is different from the situation for trees. The authors are interested in identifying exactly those unicyclic graphs which admit a simply structured kernel basis. The main result of the paper has the following form. Let \(G\) be a unicyclic graph with cycle \(C\) and let \(T_i\) be the trees emanating from \(C\). Assume that each tree \(T_i\) is attached to \(C\) by an edge \(v_iu_i\) such that \(u_i\) and \(v_i\) are vertices of \(C\) and \(T_i\), respectively. Then \(G\) has a simply structured kernel basis unless \(| C| \equiv 2\mod4\) and a particular condition holds. The authors present three different conditions, allowing to state an algorithmic, an algebraic and a structural characterization of the unicyclic graphs with simply structured kernel bases.
0 references
Unicyclic graph
0 references
Trees
0 references
Kernel
0 references
Basis
0 references
Gaussian elimination
0 references