Independence in Function Graphs

Abstract

Given two graphs $G$ and $H$ and a function $f\subset V(G)\times V(H)$, Hedetniemi [9] defined the \emph{function graph} $GfH$ by $V(GfH)=V(G)\cup V(H)$ and $E(GfH)=E(G)\cup E(H)\cup \{uv\mid v:f(u)\}$. Whenever $G\cong H$, the function graph was called a functigraph by Chen, Ferrero, Gera, and Yi [7]. A function graph is a generalization of the $\alpha$-permutation graph introduced by Chartrand and Harary [5]. The independence number of a graph is the size of a largest set of mutually non-adjacent vertices. In this paper, we study independence number in function graphs. In particular, we give a lower bound in terms of the order and the chromatic number, which improves on some elementary results and has a number of interesting corollaries.