On Graphs with Strong $\alpha$-Valuations

Abstract

The concept of a strong $a$-valuation was introduced by Maheo, who showed that if a graph $G$ has a strong $a$-valuation, then so does $G\times K_2$. We show that for various graphs $G$, $G\times Q_n$ has a strong $a$-valuation and $G\times P_n$ has an $a$-valuation, where $Q_n$ is the $n$-cube and $P_n$ the path with $n$ edges, including $G=K_{m,2}$ for any $m$. Yet we show that $K_{m,n}\times K_2$ does not have a strong $a$-valuation if $m$ and $n$ are distinct odd integers.