A Description of the Subgraph Induced at a Labeling of a Graph by the Subset of Vertices with an Interval Spectrum

Abstract

The sets of vertices and edges of an undirected, simple, finite, connected graph \(G\) are denoted by \(V(G)\) and \(E(G)\), respectively. An arbitrary nonempty finite subset of consecutive integers is called an interval. An injective mapping \(\varphi:E(G)\rightarrow \{1,2,...,|E(G)|\}\) is called a labeling of the graph \(G\). If \(G\) is a graph, \(x\) is its arbitrary vertex, and \(\varphi\) is its arbitrary 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 labeling \(\varphi\). For any graph \(G\) and its arbitrary labeling \(\varphi\), a structure of the subgraph of \(G\), induced by the subset of vertices of \(G\) with an interval spectrum, is described.