2017/08/01 by Konečný, Matěj, Kučera, Stanislav, Novotná, Jana +3
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1708.00552
A graph G is called a sum graph if there is a so-called sum labeling of G, i.e. an injective function ℓ: V(G) → ℕ such that for every u,v∈ V(G) it holds that uv∈ E(G) if and only if there exists a vertex w∈ V(G) such that ℓ(u)+ℓ(v) = ℓ(w). We say that sum labeling ℓ is minimal if there is a vertex u∈ V(G) such that ℓ(u)=1. In this paper, we show that if we relax the conditions (either allow non-injective labelings or consider graphs with loops) then there are sum graphs without a minimal labeling, which partially answers the question posed by Miller, Ryan and Smyth in 1998.