betaFeedback

WorksMathematics

Uniquely K4K_{4}-saturated graphs with large maximum degree

Abstract

A graph GG is \textit{uniquely HH-saturated} if it contains no copy of HH as a subgraph, but adding any edge to GG creates exactly one copy of HH in the resultant graph. In this paper, we consider the uniquely K4K_{4}-saturated graphs and characterize the uniquely K4K_{4}-saturated graphs on nn vertices with maximum degree Δ≥n−5Δ\geq n-5. We prove that if GG is a uniquely K4K_{4}-saturated graph with universal vertex xx, then G−xG-x is either a star or a Moore graph of diameter 2. The uniquely K4K_{4}-saturated graphs with maximum degrees n−3n-3 and n−5n-5 are C7‾\overline{C_{7}} and G10G_{10} in Figure 2, respectively. But there are no uniquely K4K_{4}-saturated graphs with maximum degree n−2n-2 or n−4n-4.

Paper details

vlnc:W_jv4z2psu
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…