NUK - logo
E-viri
Recenzirano Odprti dostop
  • On Singular Signed Graphs w...
    Bašić, Nino; Fowler, Patrick W.; Pisanski, Tomaž; Sciriha, Irene

    Discussiones Mathematicae. Graph Theory, 11/2022, Letnik: 42, Številka: 4
    Journal Article

    A signed graph has edge weights drawn from the set {+1, −1}, and is if it is equivalent to an unsigned graph under the operation of sign switching; otherwise it is . 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 ( ) for which a -regular nut graph (sign-balanced or sign-unbalanced) of order 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 = 1 exists are characterised; they are sign-unbalanced with an underlying graph for which ≡ 1 (mod 4). Orders for which a regular sign-unbalanced nut graph with = 2 exists are also characterised; they have an underlying cocktail-party graph CP( ) with even order ≥ 8.