2013/07/04 by A. M. Khachatryan, Khachatryan, A. M., R. R. Kamalian +1 · 2 citations
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1307.1389
9 pages. arXiv admin note: substantial text overlap with arXiv:1205.0125
arxiv created 2013/07/04 · arxiv updated 2013/07/05
For an undirected, simple, finite, connected graph G, we denote by V(G) and E(G) the sets of its vertices and edges, respectively. A function φ:E(G)→ \1,...,t\ is called a proper edge t-coloring of a graph G, if adjacent edges are colored differently and each of t colors is used. The least value of t for which there exists a proper edge t-coloring of a graph G is denoted by χ'(G). For any graph G, and for any integer t satisfying the inequality χ'(G)≤ t≤ |E(G)|, we denote by α(G,t) the set of all proper edge t-colorings of G. Let us also define a set α(G) of all proper edge colorings of a graph G: α(G)≡\bigcupt=χ'(G)|E(G)|α(G,t). An arbitrary nonempty finite subset of consecutive integers is called an interval. If φ∈α(G) and x∈ V(G), then the set of colors of edges of G which are incident with x is denoted by SG(x,φ) and is called a spectrum of the vertex x of the graph G at the proper edge coloring φ. If G is a graph and φ∈α(G), then define fG(φ)≡|\x∈ V(G)/SG(x,φ) \textrmis an interval\|. For a graph G and any integer t, satisfying the inequality χ'(G)≤ t≤ |E(G)|, we define: μ1(G,t)≡minφ∈α(G,t)fG(φ), μ2(G,t)≡maxφ∈α(G,t)fG(φ). For any graph G, we set: μ11(G)≡minχ'(G)≤ t≤|E(G)|μ1(G,t), μ12(G)≡maxχ'(G)≤ t≤|E(G)|μ1(G,t), μ21(G)≡minχ'(G)≤ t≤|E(G)|μ2(G,t), μ22(G)≡maxχ'(G)≤ t≤|E(G)|μ2(G,t). For any positive integer n, the exact values of the parameters μ11, μ12, μ21 and μ22 are found for the graph of the n-dimensional cube.