Nut digraphs

Bašić, Nino (author), Fowler, Patrick W. (author), McCarthy, Maxine M. (author), Potočnik, Primož (author)

A nut graph is a simple graph whose kernel is spanned by a single full vector (i.e., the adjacency matrix has a single zero eigenvalue and all non-zero kernel eigenvectors have no zero entry). We classify generalisations of nut graphs to nut digraphs: a digraph whose kernel (resp. co-kernel) is spanned by a full vector is dextro-nut (resp. laevo-nut); a bi-nut digraph is both laevo- and dextro-nut; an ambi-nut digraph is a bi-nut digraph where kernel and co-kernel are spanned by the same vector; a digraph is inter-nut if the intersection of the kernel and co-kernel is spanned by a full vector. It is known that a nut graph is connected, leafless and non-bipartite. It is shown here that an ambi-nut digraph is strongly connected, non-bipartite (i.e., has a non-bipartite underlying graph) and has minimum in-degree and minimum out-degree of at least 2. Refined notions of core and core-forbidden vertices apply to singular digraphs. Infinite families of nut digraphs and systematic coalescence, crossover and multiplier constructions are introduced. Relevance of nut digraphs to topological physics is discussed.

• Language: English
• Keywords: nut graph, core graph, nullity, directed graph, nut digraph, dextro-nut digraph, laevo-nut digraph, bi-nut digraph, ambi-nut digraph, inter-nut digraph, dextro-core vertex, laevo-core vertex, graph spectra
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Year: 2026
• Number of pages: Str. 203-226
• Numbering: Vol. 383
• PID: 20.500.12556/RUL-180418
• UDC: 519.17
• ISSN on article: 0166-218X
• DOI: 10.1016/j.dam.2025.12.037
• COBISS.SI-ID: 264177411
• Publication date in RUL: 09.03.2026

Record is a part of a journal

• Title: Discrete applied mathematics
• Shortened title: Discrete appl. math.
• Publisher: Elsevier
• ISSN: 0166-218X
• COBISS.SI-ID: 25342464

Licences

• License: CC BY 4.0, Creative Commons Attribution 4.0 International
• Link: http://creativecommons.org/licenses/by/4.0/
• Description: This is the standard Creative Commons license that gives others maximum freedom to do what they want with the work as long as they credit the author.

Secondary language

• Language: Slovenian
• Keywords: orešni graf, sredični graf, ničelnost, usmerjeni graf, orešni digraf, desnoorešni digraf, levoorešni digraf, biorešni digraf, ambiorešni digraf, interorešni digraf, desnosredično vozlišče, levosredično vozlišče, spektri grafov