13
views
0
recommends
+1 Recommend
0 collections
0
shares
• Record: found
• Abstract: found
• Article: found
Is Open Access

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

Preprint

Bookmark
There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

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 $$\delta(G)$$ and $$\eta(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\subseteq 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 $$\varphi:E(G)\rightarrow \{1,2,\dots,|E(G)|\}$$ is called an edge labeling of the graph $$G$$, if for arbitrary different edges $$e'\in E(G)$$ and $$e''\in E(G)$$, the inequality $$\varphi(e')\neq \varphi(e'')$$ holds. If $$G$$ is a graph, $$x$$ is its arbitrary vertex, and $$\varphi$$ is its arbitrary edge labeling, then the set $$S_G(x,\varphi)\equiv\{\varphi(e)/ e\in E(G), e \textrm{is incident with} x$$\} is called a spectrum of the vertex $$x$$ of the graph $$G$$ at its edge labeling $$\varphi$$. If $$G$$ is a graph and $$\varphi$$ is its arbitrary edge labeling, then $$V_{int}(G,\varphi)\equiv\{x\in V(G)/\;S_G(x,\varphi)\textrm{is an interval}\}$$. For an arbitrary $$r$$-regular graph $$G$$ with $$r\geq2$$ and its arbitrary edge labeling $$\varphi$$, the inequality $|V_{int}(G,\varphi)|\leq\bigg\lfloor\frac{3\cdot|V(G)|-2\cdot\eta(G[V_{int}(G,\varphi)])}{4}\bigg\rfloor.$ is proved.

Author and article information

Journal
1307.1392

Combinatorics, Discrete mathematics & Graph theory