On Friendly Index Sets of Root-unions of Stars By Cycles

Yong-Song Ho1, Sin-Min Lee2, Ho Kuen Ng3
1Nan Chiao High School Singapore
2Department of Computer Science San Jose State University San Jose, CA 95192, USA
3Department of Mathematics San Jose State University San Jose, CA 95192, USA

Abstract

Let \( G \) be a graph with vertex set \( V(G) \) and edge set \( E(G) \). A labeling \( f: V(G) \to \mathbb{Z}_2 \) induces an edge labeling \( f^*: E(G) \to \mathbb{Z}_2 \), defined by \( f^*(xy) = f(x) + f(y) \), for each edge \( xy \in E(G) \). For \( i \in \mathbb{Z}_2 \), let

\[
\text{v}_f(i) = \text{card}\{ v \in V(G) : f(v) = i \}
\]

and

\[
\text{e}_f(i) = \text{card}\{ e \in E(G) : f^*(e) = i \}.
\]

A labeling \( f \) of a graph \( G \) is said to be friendly if

\[
\lvert \text{v}_f(0) – \text{v}_f(1) \rvert \leq 1.
\]

The friendly index set of the graph \( G \), \( FI(G) \), is defined as

\[
\{ \lvert \text{e}_f(0) – \text{e}_f(1) \rvert : \text{the vertex labeling } f \text{ is friendly} \}.
\]

This is a generalization of graph cordiality. We introduce a graph construction called the root-union and investigate when gaps exist in the friendly index sets of root-unions of stars by cycles.

Keywords: vertex labeling, friendly labeling, cordiality, friendly index set, cycle, star, arithmetic progression.