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

Original · EN

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 φ:E(G)→ {1,2,...,|E(G)|} is called a labeling of the graph G. If G is a graph, x is its arbitrary vertex, and φ is its arbitrary labeling, then the set SG(x,φ)≡{φ(e)/ e∈ E(G), e is incident with x} is called a spectrum of the vertex x of the graph G at its labeling φ. For any graph G and its arbitrary labeling φ, a structure of the subgraph of G, induced by the subset of vertices of G with an interval spectrum, is described.