Magic powers of graphs. (English) Zbl 0889.05067

Trenkler, M.; Vetchý, V.

Math. Bohem. 122, No. 2, 121-124 (1997).

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\).

Reviewer: B.Zelinka (Liberec)

MSC:

05C78

Graph labelling (graceful graphs, bandwidth, etc.)

Keywords:

magic graph; power of graph; factor of graph