Article View

Degree Sequences and Secure Domination Variants in Connected Graphs of Order at Most Five

DOI: 10.66838/ma.229

RAYAPROLU VISWA PRASAD Research Scholar, SCSVMV, Kanchipuram, Tamil Nadu, India
KONDA SRINIVASARAO Professor of Mathematics, SCSVMV, Kanchipuram, Tamil Nadu, India

Abstract

Secure domination models a movable guard system: every unoccupied vertex must have a neighboring guard that can move to it without destroying the required protection. This paper gives a complete, graph-by-graph classification of the secure domination number, secure total domination number, and secure connected domination number for every connected non-isomorphic simple graph of order from two through five. The corpus contains exactly thirty graphs: one of order two, two of order three, six of order four, and twenty-one of order five. For each graph, the paper records a labeled diagram, edge set, nonincreasing degree sequence, a representative minimum secure set for each variant, the three parameter values, and an explicit defender certificate. The values were obtained by exhaustive subset enumeration and reproduced by an independently written bitset implementation. The classification yields ninety exact parameter values. Four complete graphs satisfy ; four noncomplete graphs satisfy ; and the remaining twenty-two graphs satisfy . Thus, among noncomplete connected graphs of order at most five, secure total and secure connected domination coincide throughout the census. The thirty graphs realize twenty-eight-degree sequences. The two repeated degree sequences occur in non-isomorphic pairs, but each pair has the same parameter triple; consequently, the degree sequence determines the triple within this finite corpus, although not in general. General results proved in the paper include the basic parameter inequalities, the ordering  for noncomplete connected graphs, exact values for complete graphs and stars, and a characterization of graphs with . The resulting article is intended as a transparent small-order reference, a source of worked examples, and a verified base for later structural conjectures.

Keywords

secure domination; secure total domination; secure connected domination; degree sequence; graph atlas; exhaustive enumeration; defender certificate; small graphs,