62
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
      ,

      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.

          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
          2013-07-04
          Article
          1307.1392
          8159aa2c-6279-4f96-8c95-150f23caf075

          http://creativecommons.org/licenses/by/3.0/

          History
          Custom metadata
          3 pages
          math.CO cs.DM

          Combinatorics,Discrete mathematics & Graph theory
          Combinatorics, Discrete mathematics & Graph theory

          Comments

          Comment on this article