## Magic powers of graphs.(English)Zbl 0889.05067

The concept of magic graph was introduced by J. Sedláček. A valuation of the edges of a graph by pairwise different positive numbers is called magic, if the sum of values of edges incident with a given vertex is the same for all vertices. If there exists a magic valuation of a graph $$G$$, then $$G$$ is called a magic graph. The $$i$$th power of a graph $$G$$ is a graph whose vertex set coincides with that of $$G$$ and in which two distinct vertices are adjacent if and only if their distance in $$G$$ is at least $$i$$. An $$I$$-graph is a graph with a linear factor, each of whose edges is incident with a vertex of degree 1 in $$G$$. The symbol $$P_5$$ denotes a path of length 5. The main theorem states that for a graph $$G$$ with at least 5 vertices its $$i$$th power $$G^i$$ is magic for all $$i\geq 3$$ and $$G^2$$ is magic if and only if $$G$$ is neither an $$I$$-graph, nor $$P_5$$.

### MSC:

 05C78 Graph labelling (graceful graphs, bandwidth, etc.)

### Keywords:

magic graph; power of graph; factor of graph
Full Text: