Isomorphic Factorization
المؤلف:
Gardner, M
المصدر:
"Ramsey Theory." Ch. 17 in Penrose Tiles and Trapdoor Ciphers... and the Return of Dr. Matrix, reissue ed. New York: W. H. Freeman
الجزء والصفحة:
...
18-5-2022
1549
Isomorphic Factorization
Isomorphic factorization colors the edges a given graph 
with 
colors so that the colored subgraphs are isomorphic. The graph 
is then 
-splittable, with 
as the divisor, and the subgraph as the factor.
When a complete graph is 2-split, a self-complementary graph results. Similarly, an 
-regular class 1 graph can be 
-split into graphs consisting of disconnected edges, making 
the edge chromatic number.
The complete graph 
can be 3-split into identical planar graphs.
Some Ramsey numbers have been bounded via isomorphic factorizations. For instance, the complete graph 
has the Clebsch graph as a factor, proving 
(Gardner 1989). That is, the complete graph on 16 points can be three-colored so that no triangle of a single color appears. (In 1955, 
was proven.)
In addition, 
can be 8-split with the Petersen graph as a factor, or 5-split with a doubled cubical graph as a factor (shown by Exoo in 2005).
The Hoffman-Singleton graph is 7-splittable into edges (shown by Royle in 2004). Whether the Hoffman-Singleton graph is a factor of 
via another 7-split is an unsolved problem.
REFERENCES
Farrugia, A. "Self-complementary Graphs and Generalizations: A Comprehensive Reference Manual." Masters Thesis. University of Malta, 1999. http://members.lycos.co.uk/afarrugia/sc-graph/sc-graph-survey.ps.
Gardner, M. "Ramsey Theory." Ch. 17 in Penrose Tiles and Trapdoor Ciphers... and the Return of Dr. Matrix, reissue ed. New York: W. H. Freeman, pp. 231-247, 1989.
West, D. "Hoffman-Singleton Decomposition of 
." http://www.math.uiuc.edu/~west/openp/hoffsing.html.
الاكثر قراءة في نظرية البيان
اخر الاخبار
اخبار العتبة العباسية المقدسة
