EXISTENCE OF REGULAR NUT GRAPHS AND THE FOWLER CONSTRUCTION

In this paper the problem of the existence of regular nut graphs is addressed. A generalization of Fowler’s Construction which is a local enlargement applied to a vertex in a graph is introduced to generate nut graphs of higher order. Let N(ρ) denote the set of integers n such that there exists a re...

Full description

Saved in:
Bibliographic Details
Published in:Applicable analysis and discrete mathematics 2023, Vol.17 (2), p.321-333
Main Authors: Gauci, John Baptist, Pisanski, Tomaž, Sciriha, Irene
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In this paper the problem of the existence of regular nut graphs is addressed. A generalization of Fowler’s Construction which is a local enlargement applied to a vertex in a graph is introduced to generate nut graphs of higher order. Let N(ρ) denote the set of integers n such that there exists a regular nut graph of degree ρ and order n. It is proven that N(3) = {12} ∪ {2k : k ≥ 9} and that N(4) = {8, 10, 12} ∪ {n : n ≥ 14}. The problem of determining N(ρ) for ρ > 4 remains completely open.
ISSN:1452-8630
2406-100X
DOI:10.2298/AADM190517028G