On Singular Signed Graphs with Nullspace Spanned by a Full Vector: Signed Nut Graphs
A signed graph has edge weights drawn from the set {+1, −1}, and is sign-balanced if it is equivalent to an unsigned graph under the operation of sign switching; otherwise it is sign-unbalanced. A nut graph has a one dimensional kernel of the 0-1 adjacency matrix with a corresponding eigenvector tha...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
University of Zielona Góra
2022-11-01
|
| Series: | Discussiones Mathematicae Graph Theory |
| Subjects: | |
| Online Access: | https://doi.org/10.7151/dmgt.2436 |
| _version_ | 1797717930303029248 |
|---|---|
| author | Bašić Nino Fowler Patrick W. Pisanski Tomaž Sciriha Irene |
| author_facet | Bašić Nino Fowler Patrick W. Pisanski Tomaž Sciriha Irene |
| author_sort | Bašić Nino |
| collection | DOAJ |
| description | A signed graph has edge weights drawn from the set {+1, −1}, and is sign-balanced if it is equivalent to an unsigned graph under the operation of sign switching; otherwise it is sign-unbalanced. A nut graph has a one dimensional kernel of the 0-1 adjacency matrix with a corresponding eigenvector that is full. In this paper we generalise the notion of nut graphs to signed graphs. Orders for which regular nut graphs with all edge weights +1 exist have been determined recently for the degrees up to 12. By extending the definition to signed graphs, we here find all pairs (ρ, n) for which a ρ-regular nut graph (sign-balanced or sign-unbalanced) of order n exists with ρ ≤ 11. We devise a construction for signed nut graphs based on a smaller ‘seed’ graph, giving infinite series of both sign-balanced and sign-unbalanced ρ -regular nut graphs. Orders for which a regular nut graph with ρ = n − 1 exists are characterised; they are sign-unbalanced with an underlying graph Kn for which n ≡ 1 (mod 4). Orders for which a regular sign-unbalanced nut graph with ρ = n − 2 exists are also characterised; they have an underlying cocktail-party graph CP(n) with even order n ≥ 8. |
| first_indexed | 2024-03-12T08:43:36Z |
| format | Article |
| id | doaj.art-221fe9ffabd3402a8d36b710857fa045 |
| institution | Directory Open Access Journal |
| issn | 2083-5892 |
| language | English |
| last_indexed | 2024-03-12T08:43:36Z |
| publishDate | 2022-11-01 |
| publisher | University of Zielona Góra |
| record_format | Article |
| series | Discussiones Mathematicae Graph Theory |
| spelling | doaj.art-221fe9ffabd3402a8d36b710857fa0452023-09-02T16:32:48ZengUniversity of Zielona GóraDiscussiones Mathematicae Graph Theory2083-58922022-11-014241351138210.7151/dmgt.2436On Singular Signed Graphs with Nullspace Spanned by a Full Vector: Signed Nut GraphsBašić Nino0Fowler Patrick W.1Pisanski Tomaž2Sciriha Irene3FAMNIT, University of Primorska, Koper, Slovenia, and IAM, University of Primorska, Koper, Slovenia, and Institute of Mathematics, Physics and Mechanics, Ljubljana, SloveniaDepartment of Chemistry, University of Sheffield, Sheffield S3 7HF, UKFAMNIT, University of Primorska, Koper, Slovenia, and IAM, University of Primorska, Koper, Slovenia, and Institute of Mathematics, Physics and Mechanics, Ljubljana, Slovenia, and Faculty of Mathematics and Physics, University of Ljubljana, Ljubljana, SloveniaDepartment of Mathematics, Faculty of Science, University of Malta, Msida, MaltaA signed graph has edge weights drawn from the set {+1, −1}, and is sign-balanced if it is equivalent to an unsigned graph under the operation of sign switching; otherwise it is sign-unbalanced. A nut graph has a one dimensional kernel of the 0-1 adjacency matrix with a corresponding eigenvector that is full. In this paper we generalise the notion of nut graphs to signed graphs. Orders for which regular nut graphs with all edge weights +1 exist have been determined recently for the degrees up to 12. By extending the definition to signed graphs, we here find all pairs (ρ, n) for which a ρ-regular nut graph (sign-balanced or sign-unbalanced) of order n exists with ρ ≤ 11. We devise a construction for signed nut graphs based on a smaller ‘seed’ graph, giving infinite series of both sign-balanced and sign-unbalanced ρ -regular nut graphs. Orders for which a regular nut graph with ρ = n − 1 exists are characterised; they are sign-unbalanced with an underlying graph Kn for which n ≡ 1 (mod 4). Orders for which a regular sign-unbalanced nut graph with ρ = n − 2 exists are also characterised; they have an underlying cocktail-party graph CP(n) with even order n ≥ 8.https://doi.org/10.7151/dmgt.2436signed graphnut graphsingular graphgraph spectrumfowler constructionsign-balanced graphsign-unbalanced graphcocktail-party graph05c5015a1805c2205c92 |
| spellingShingle | Bašić Nino Fowler Patrick W. Pisanski Tomaž Sciriha Irene On Singular Signed Graphs with Nullspace Spanned by a Full Vector: Signed Nut Graphs Discussiones Mathematicae Graph Theory signed graph nut graph singular graph graph spectrum fowler construction sign-balanced graph sign-unbalanced graph cocktail-party graph 05c50 15a18 05c22 05c92 |
| title | On Singular Signed Graphs with Nullspace Spanned by a Full Vector: Signed Nut Graphs |
| title_full | On Singular Signed Graphs with Nullspace Spanned by a Full Vector: Signed Nut Graphs |
| title_fullStr | On Singular Signed Graphs with Nullspace Spanned by a Full Vector: Signed Nut Graphs |
| title_full_unstemmed | On Singular Signed Graphs with Nullspace Spanned by a Full Vector: Signed Nut Graphs |
| title_short | On Singular Signed Graphs with Nullspace Spanned by a Full Vector: Signed Nut Graphs |
| title_sort | on singular signed graphs with nullspace spanned by a full vector signed nut graphs |
| topic | signed graph nut graph singular graph graph spectrum fowler construction sign-balanced graph sign-unbalanced graph cocktail-party graph 05c50 15a18 05c22 05c92 |
| url | https://doi.org/10.7151/dmgt.2436 |
| work_keys_str_mv | AT basicnino onsingularsignedgraphswithnullspacespannedbyafullvectorsignednutgraphs AT fowlerpatrickw onsingularsignedgraphswithnullspacespannedbyafullvectorsignednutgraphs AT pisanskitomaz onsingularsignedgraphswithnullspacespannedbyafullvectorsignednutgraphs AT scirihairene onsingularsignedgraphswithnullspacespannedbyafullvectorsignednutgraphs |