Let N be any integer. Can we define some graphs with vertex set as the partitions of N? If so, is there any literature is available?
This is a good question.
Integer distance graphs are explored in
J.-H. Kang, Combinatorial number theory,:
http://www.westga.edu/~jkang/CNumTh.pdf
Taking this a step further, consider
D.R. Wood, Acyclic, star and oriented colourings of graph subdivisions, Discrete Math. and Theor. Comp. Sci. 7, 2005, 37-50:
http://www.emis.de/journals/DMTCS/pdfpapers/dm070104.pdf
See Theorem 1, p. 39, which gives a condition for a d-degenerate graph with a vertex partition based on non-negative integers. There are 40 places in this article where vertex partitions are discussed.
Two trees on integer partitions
http://11011110.livejournal.com/5126.html
Another partial cube of partitions
http://11011110.livejournal.com/6130.html
What is the dimension of the set of partitions?
http://11011110.livejournal.com/6402.html
Hyper graph is the exampe for grouping the vertices. Similar vertices can be grouped and the edges are between the groups.
Let P,Q be two partitions of n. Then P is called a refinement of Q if it can be obtained by partitioning some parts of Q. The set of all partitions of n is partially ordered by the refinement relation. Now we can consider either the comparability graph or the Hasse diagram of this poset. Thus, P and Q are adjacent in the comparability graph if (say) P is a refinement of Q, and they are adjacent in the Hasse diagram if, moreover, there is no partition lying properly between them.
- Badges
- Science topic
- Similar topics
- Mathematical Sciences
- Graphs