Blog
About

  • 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

Read this article at

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.

      Related collections

      Author and article information

      Journal
      1307.1392

      Combinatorics, Discrete mathematics & Graph theory

      Comments

      Comment on this article