1. Non-Singular graphs with a Singular Deck.
- Author
-
Farrugia, Alexander, Gauci, John Baptist, and Sciriha, Irene
- Subjects
- *
GRAPH theory , *MATHEMATICAL symmetry , *MATRICES (Mathematics) , *MOLECULAR graphs , *ELECTRICAL conductors , *SUBGRAPHS - Abstract
The n -vertex graph G ( = Γ ( G ) ) with a non-singular real symmetric adjacency matrix G , having a zero diagonal and singular ( n − 1 ) × ( n − 1 ) principal submatrices is termed a NSSD, a Non-Singular graph with a Singular Deck. NSSDs arose in the study of the polynomial reconstruction problem and were later found to characterise non-singular molecular graphs that are distinct omni-conductors and ipso omni-insulators. Since both matrices G and G − 1 represent NSSDs Γ ( G ) and Γ ( G − 1 ) , the value of the nullity of a one-, two- and three-vertex deleted subgraph of G is shown to be determined by the corresponding subgraph in Γ ( G − 1 ) . Constructions of infinite subfamilies of non-NSSDs are presented. NSSDs with all two-vertex deleted subgraphs having a common value of the nullity are referred to as G -nutful graphs. We show that their minimum vertex degree is at least 4. [ABSTRACT FROM AUTHOR]
- Published
- 2016
- Full Text
- View/download PDF