TOPICS
Search

Twisted Isaacs Graph


A twisted Isaacs graph is a cubic graph obtained by closing a chain of n claw graphs with a permutation pi of their three leaves (Nedela and Škoviera 2022). For integer n>=3, take vertices t_i, x_i, y_i, and z_i for i=1, ..., n. Join t_i to x_i, y_i, and z_i, and join equally lettered vertices at consecutive indices. Finally join x_n, y_n, and z_n to pi(x)_1, pi(y)_1, and pi(z)_1, respectively. The result has 4n vertices and 6n edges.

For each n, there are three non-isomorphic cases, denoted FS(k,n) by Fouquet et al. (2010). The parameter k counts the cycles remaining after the vertices t_i are deleted, not the order of the closing permutation. A 3-permutation cycle gives FS(1,n), with one remaining cycle graph C_(3n). A transposition gives FS(2,n), with remaining cycle graphs C_n and C_(2n). The identity permutation gives FS(3,n), with three remaining cycle graphs C_n. All three cases, including the identity permutation, are called twisted Isaacs graphs by Nedela and Škoviera (2022).

The case FS(2,n) is also called an Isaacs graph (Nedela and Škoviera 2022). Some named special cases are summarized in the following table.

Zheng et al. (2008, Lemmas 4.2, 4.3, and 4.8) determine the graph crossing number of FS(2,n) as

 cr(FS(2,n))={n-1   for 3<=n<=5; n   for n>=6.
(1)

The abstract and introduction of Zheng et al. (2008) incorrectly print n-2 in the first case, giving 1, 2, and 3 for n=3, 4, and 5. Lemmas 4.2 and 4.3 establish the correct values 2, 3, and 4.

For every integer n>=3, the graph crossing number of FS(3,n) is at most n. To see this, draw its three cycles as concentric circles and place the claw graphs in separate angular sectors, each with exactly one crossing of the middle cycle graph. The graph crossing number of FS(3,n) is known to equal n at least for n=10, 12, and 14.

The number of perfect matchings in all three cases is

 mu(FS(k,n))=2^n+(1+(-1)^n)3^(n/2)+(-1)^nc_k,
(2)

where c_1=-1, c_2=0, and c_3=2 (Fouquet et al. 2010, Theorem 5). The three counts are distinct for each n, which also proves that the three cases are non-isomorphic.

All three cases have girth 6 and cyclic edge connectivity 6 for n>=6. For k=1, both conclusions already hold for n>=4 (Nedela and Škoviera 2022, Proposition 4.1).


See also

Cubic Graph, Flower Graph, Flower Snark, Starfish Graph, Tietze Graph, Triplex Graph

Explore with Wolfram|Alpha

References

Fouquet, J.-L.; Thuillier, H.; and Vanherpe, J.-M. "On a Family of Cubic Graphs Containing the Flower Snarks." Discuss. Math. Graph Theory 30, 289-314, 2010. https://doi.org/10.7151/dmgt.1495.House of Graphs. Twisted Isaacs Graphs. Triplex, Tietzes Graph, Starfish Graph, Flower Snark J5, Two-orbit graph, Flower Snark J7, Flower Snark J9, and Flower Snark J11.Nedela, R. and Škoviera, M. "Cyclic Connectivity, Edge-Elimination, and the Twisted Isaacs Graphs." J. Combin. Th. Ser. B 155, 17-44, 2022. https://doi.org/10.1016/j.jctb.2022.01.007.Zheng, W.; Lin, X.; Yang, Y.; and Yang, X. "The Crossing Number of Flower Snarks and Related Graphs." Ars Combin. 86, 57-64, 2008. https://combinatorialpress.com/ars-articles/volume-086-ars-articles/the-crossing-number-of-flower-snarks-and-related-graphs/.

Cite this as:

Weisstein, Eric W. "Twisted Isaacs Graph." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TwistedIsaacsGraph.html

Subject classifications