Independence in Function Graphs

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.