+1 Recommend
0 collections
      • 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


      Read this article at

          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.


          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.

          Related collections

          Combinatorics, Discrete mathematics & Graph theory


          Comment on this article