2013/07/04 by Narine N. Davtyan, N. N. Davtyan, Davtyan, N. N. +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Graph theory and applications #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1307.1392
3 pages
arxiv created 2013/07/04 · openalex publication_date 2013/07/04 · arxiv updated 2013/07/05 · openalex created_date 2016/06/24 · openalex updated_date 2026/07/28
We consider undirected simple finite graphs. The sets of vertices and edges of a graph G are denoted by V(G) and E(G), respectively. For a graph G, we denote by δ(G) and η(G) the least degree of a vertex of G and the number of connected components of G, respectively. For a graph G and an arbitrary subset V0⊆ V(G) G[V0] denotes the subgraph of the graph G induced by the subset V0 of its vertices. An arbitrary nonempty finite subset of consecutive integers is called an interval. A function φ:E(G)→ \1,2,…,|E(G)|\ is called an edge labeling of the graph G, if for arbitrary different edges e'∈ E(G) and e''∈ E(G), the inequality φ(e')≠ φ(e'') holds. If G is a graph, x is its arbitrary vertex, and φ is its arbitrary edge labeling, then the set SG(x,φ)≡\φ(e)/ e∈ E(G), e \textrmis incident with x\ is called a spectrum of the vertex x of the graph G at its edge labeling φ. If G is a graph and φ is its arbitrary edge labeling, then Vint(G,φ)≡\x∈ V(G)/ SG(x,φ)\textrmis an interval\. For an arbitrary r-regular graph G with r≥2 and its arbitrary edge labeling φ, the inequality |Vint(G,φ)|≤\lfloor\frac3⋅|V(G)|-2⋅η(G[Vint(G,φ)])4\rfloor. is proved.