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 $\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 $\phi :E(G)\to \{1,2,\dots ,|E(G)|\}$ is called an edge labeling of the graph $G$, if for arbitrary different edges $e^{\prime }\in E(G)$ and $e^{\prime \prime }\in E(G)$, the inequality $\phi (e^{\prime })\ne \phi (e^{\prime \prime })$ holds. If $G$ is a graph, $x$ is its arbitrary vertex, and $\phi$ is its arbitrary edge labeling, then the set $S_G(x,\phi )\equiv \{\phi (e)/e\in E(G),e\text{is incident with}x$\} is called a spectrum of the vertex $x$ of the graph $G$ at its edge labeling $\phi$. If $G$ is a graph and $\phi$ is its arbitrary edge labeling, then $V_{int}(G,\phi )\equiv \{x\in V(G)/S_G(x,\phi )\text{is an interval}\}$. For an arbitrary $r$-regular graph $G$ with $r\ge 2$ and its arbitrary edge labeling $\phi$, the inequality $$|V_{int}(G,\phi )|\le \lfloor \frac{3\cdot |V(G)|-2\cdot \eta (G[V_{int}(G,\phi )])}{4}\rfloor .$$ is proved.

3 pages

Cited by in corpus (1)

• Some remarks on relations between the $\mu$-parameters of regular graphs