STRUCTURAL PROPERTIES OF I-GRAPHS: THEIR INDEPENDENCE NUMBERS AND CAYLEY GRAPHS

NEW

Problem: Reconstructed conjecture: For every proper I-graph $I(n,j,k)$, either the $k$-grouping construction or the $j$-grouping construction yields a maximum independent set. Here

$$V(I(n,j,k))=\{a_i,b_i:i\in\mathbb Z_n\},$$

with edges $a_i a_{i+j}, a_i b_i, b_i b_{i+k}$. Following the thesis terminology, a $k$-grouping is $k$ consecutively indexed vertices from $B=\{b_i\}$, and a $j$-grouping is $j$ consecutively indexed vertices from $A=\{a_i\}$. The reconstruction is supported by Dods’s parallel thesis, which defines these groupings and states the same future-work conjecture.

Result: The conjecture is false. A counterexample is

$$I(30,3,5).$$

It is a proper I-graph because

$$\gcd(30,3,5)=1,\qquad \gcd(30,3)=3>1,\qquad \gcd(30,5)=5>1,$$

so it is connected and not a generalized Petersen graph.

First, $\alpha(I(30,3,5))=30$. The spokes $a_i b_i$ form a matching of size $30$, so every independent set has size at most $30$. The set

$$S=\{a_i:i\text{ even}\}\cup\{b_i:i\text{ odd}\}$$

is independent: $3$ and $5$ are odd, so outer and inner skip edges always change parity, and no spoke has both endpoints in $S$. Hence $|S|=30$, so $\alpha=30$.

Now let $T$ be any maximum independent set. Since $|T|=30$, $T$ contains exactly one of $a_i,b_i$ for each $i$. Let

$$X=\{i:a_i\in T\}.$$

Then $X$ contains no two indices differing by $3$, while $\mathbb Z_{30}\setminus X$ contains no two indices differing by $5$.

The graph on $\mathbb Z_{30}$ with edges $i\sim i+3$ is three $10$-cycles, so $|X|\le 15$. The graph with edges $i\sim i+5$ is five $6$-cycles, so $|\mathbb Z_{30}\setminus X|\le15$, hence $|X|\ge15$. Thus $|X|=15$, and $X$ is a maximum independent set on each $10$-cycle, so

$$1_X(i+3)=1-1_X(i).$$

Similarly,

$$1_X(i+5)=1-1_X(i).$$

Therefore $1_X(i+2)=1_X(i)$, so $X$ is constant on parity classes, and the $+3$ relation forces the two parity classes to have opposite values. Thus the only maximum independent sets are the two parity sets.

Neither parity maximum contains three consecutive $a$-vertices or five consecutive $b$-vertices. Hence no maximum independent set contains a $j$-grouping or a $k$-grouping, so neither grouping construction can yield a maximum independent set for $I(30,3,5)$.

Citation: No prior resolution is used. Definitions are from Matthew S. Dods, Independence Number of Specified I-Graphs, M.S. thesis, Naval Postgraduate School, 2020, §3.2.