On the extremal values of the number of vertices with an interval spectrum on the set of proper edge colorings of the graph of the $n$-dimensional cube

Abstract

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 $\phi :E(G)\to \{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 ${\chi }^{\prime }(G)$. For any graph $G$, and for any integer $t$ satisfying the inequality ${\chi }^{\prime }(G)\le t\le |E(G)|$, we denote by $\alpha (G,t)$ the set of all proper edge $t$-colorings of $G$. Let us also define a set $\alpha (G)$ of all proper edge colorings of a graph $G$: $$\alpha (G)\equiv \bigcup _{t={\chi }^{\prime }(G)}^{|E(G)|}\alpha (G,t).$$ An arbitrary nonempty finite subset of consecutive integers is called an interval. If $\phi \in \alpha (G)$ and $x\in V(G)$, then the set of colors of edges of $G$ which are incident with $x$ is denoted by $S_G(x,\phi )$ and is called a spectrum of the vertex $x$ of the graph $G$ at the proper edge coloring $\phi$. If $G$ is a graph and $\phi \in \alpha (G)$, then define $f_G(\phi )\equiv |\{x\in V(G)/S_G(x,\phi )\text{is an interval}\}|$. For a graph $G$ and any integer $t$, satisfying the inequality ${\chi }^{\prime }(G)\le t\le |E(G)|$, we define: $${\mu }_1(G,t)\equiv \underset{\phi \in \alpha (G,t)}{\min }{f}_G(\phi ),{\mu }_2(G,t)\equiv \underset{\phi \in \alpha (G,t)}{\max }{f}_G(\phi ).$$ For any graph $G$, we set: $${\mu }_{11}(G)\equiv \underset{{\chi }^{\prime }(G)\le t\le |E(G)|}{\min }{\mu }_1(G,t),{\mu }_{12}(G)\equiv \underset{{\chi }^{\prime }(G)\le t\le |E(G)|}{\max }{\mu }_1(G,t),$$ $${\mu }_{21}(G)\equiv \underset{{\chi }^{\prime }(G)\le t\le |E(G)|}{\min }{\mu }_2(G,t),{\mu }_{22}(G)\equiv \underset{{\chi }^{\prime }(G)\le t\le |E(G)|}{\max }{\mu }_2(G,t).$$ For any positive integer $n$, the exact values of the parameters ${\mu }_{11}$, ${\mu }_{12}$, ${\mu }_{21}$ and ${\mu }_{22}$ are found for the graph of the $n$-dimensional cube.

9 pages. arXiv admin note: substantial text overlap with arXiv:1205.0125

References in corpus (1)

• Interval colorings of edges of a multigraph

Cited by in corpus (2)

• Some remarks on relations between the $\mu$-parameters of regular graphs
• On the $\mu$-parameters of the Petersen graph