An inequality for the number of vertices with an interval spectrum in edge labelings of regular graphs

Abstract: 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

d e l t a (G)

and

e t a (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

V_{0} s u b s e t e q V (G)

G [V_{0}]

denotes the subgraph of the graph

G

induced by the subset

V_{0}

of its vertices. An arbitrary nonempty finite subset of consecutive integers is called an interval. A function

v a r p h i : E (G) i g h t a r r o w 1, 2, d o t s, | E (G) |

is called an edge labeling of the graph

G

, if for arbitrary different edges

e^{'} i n E (G)

and

e^{″} i n E (G)

, the inequality

v a r p h i (e^{'}) e q v a r p h i (e^{″})

holds. If

G

is a graph,

x

is its arbitrary vertex, and

v a r p h i

is its arbitrary edge labeling, then the set

} is called a spectrum of the vertex

x

of the graph

G

at its edge labeling

v a r p h i

. If

G

is a graph and

v a r p h i

is its arbitrary edge labeling, then

V_{i n t} (G, v a r p h i) e q u i v x i n V (G) /; S_{G} (x, v a r p h i) e x t r m i s a n i n t e r v a l

. For an arbitrary

r

-regular graph

G

with

r g e q 2

and its arbitrary edge labeling

v a r p h i

, the inequality

|V_{int}(G,varphi)|leq�igglfloorfrac{3cdot|V(G)|-2cdoteta(G[V_{int}(G,varphi)])}{4}�igg floor.

is proved.

This page was built for publication: An inequality for the number of vertices with an interval spectrum in edge labelings of regular graphs