# Some properties of graphical partitions.

Introduction

The various Properties relating to partitions of a number and its graphical partitions have already been established. There are so many relations and properties of partition functions. It is found that some of the asymptotic behaviours of the partition function have been forwarded by G.H. Hardy and S. Ramanujan (1918). They mainly focused the circular method of the partition function. The application of partition function is found mainly in the areas of Analytical Number Theory, Analysis and Algebric Geometry. It needs to mention that the pentagonal numbers have some structures of a graph but these structures are not graphical. Though we study the partition functions having different applications in number theory, the graphical partitions admitting graphs but satisfies Handseeking lemma of graph theory is possible only in case of even numbers . It is not so easy to find out a functional relationship or a recurring relation between graphical partition functions for even number 'n', as the numerical value of the graphical partition functions increases considerably with n. Again, it is not an easy task to find the number of graphical partitions of an even number though Erdos and Gallai  have found some relationship which could not solve the problem of calculating the graphical partitions of the numbers. Some Results of partition of even number which are graphical or non graphical are reported by Erdos and Richmond . They established two results by showing the bounds for g(n), the graphical partition of n .They found that all partitions in R(n), the set of partition of n for which all rank vector entries are negative, are graphical and hence g(n) [greater than or equal to] r(n)= [absolute value of R(n)] (where r(n) is the number of partitions of n with negative successive ranks). They further observed that r(n) = p(n)- p(n-1) from the works of D.Bressound  and p(n) - p(n-1)~([pi]/[square root of (6n)]).p(n) , from the works of Roth and Szekeres  to conclude that [lim.sub.n] [right arrow][infinity]([square root of (n)].g(n))/p(n)[greater than or equal to] [pi]/[square root of (6)] (where p(n) denotes the number of unrestricted partitions of n). Moreover, how we efficiently count and generate graphical basis partitions and how to use them to count graphical partitions, that was investigated by J.M.Nolan et.al . They reported that the fraction of basis partition of n which are graphical approaches the same limit as the fraction of all partitions which are graphical, that is [lim.sub.n [right arrow][infinity]] h (n)/b(n) = [lim.sub.n [right arrow][infinity]] g(n)/p(n). However, B. pittel  has shown finally that g(n)/p(n) [right arrow] 0 as n[right arrow] [infinity] (which is an open question, originally posed by H.S. Wilf/Wilfs conjecture). A relation of the number of graphical forest partition of 2k has been found by Deborah A. Frank et. al . Although, many authors have tried to find a close formula for g(n) , still it remains under investigations.

In this paper we consider only those partitions of number n possessing graphical sequence. A partition of a non negative integer n is a finite unordered sequence of non negative integers [n.sub.1], [n.sub.2], [n.sub.3],..... whose sum is n. The partition function p (n) is defined as the number of partitions of n. Again, a graphical sequence means a sequence whose terms represent the degrees of the vertices in a simple graph, viz. a graph that can be drawn without any multiple edges or loops. The partition of a graph is the partition of 2q as the sum of the degrees of the vertices, 2q = [summation] [d.sub.i] (Handseeking Lemma). Thus a partition of [summation] [d.sub.i] of the number n into p-parts is graphical if there exists a graph G whose points have degrees [d.sub.i]. Here we have studied some theoretical investigation relating to the existence of binary tree, regular graphs having degree 1 and degree 2 and the complete graph from the graphical parts of the numbers (2n + 4), (4n + 4), (n + 1)(n + 2), (6n + 2) for n [greater than or equal to] 1 .We also get some structures from the graphical partitions of some even numbers which satisfy the saturated Hydro-carbon [C.sub.n][H.sub.2n + 2] of chemistry. An algorithm has been developed to find out the various forms of graphs among all graphical parts.

The paper is organized as follows: In section (2), we establish some theorems relating to some special type of even numbers. In section (3) we present an algorithm to generate various structures of graph of the graphical parts. Discussion is included in section (4).

Some theorems and their proofs:

Theorem (2.1): In all the graphical partitions of the numbers (2n + 4), n [greater than or equal to] 1 there always exists at least two regular graphs having degree(s) 1 and 2.

Proof: Case-(1): (Regular graph of degree 1).

For n = 1, 2n + 4 = 6.Then the graphical partition 1 + 1 + 1 + 1 + 1 + 1 of 6 gives us a regular graph of degree 1 as shown in the figure (1.1).

[FIGURE 1.1 OMITTED]

[FIGURE 1.2 OMITTED]

Suppose, there exist a regular graph of degree 1 for n=k in the graphical partitions of the number (2n + 4). Then 2k + 4 = 2(k + 2) =(1 + 1) + (1 + 1) + .......... + (1 + 1) =(k + 2) times of (1 + 1). Now if we introduce two new vertex and joining them by an edge, then the resulting graph will also be a regular graph of degree 1 which represents the partition (1 + 1) + (1 + 1) + ... + (1 + 1) of (2k + 4) + 2 i.e. {2(k + 1) + 4}. Thus, the result is true for n = k + 1 when it is true for n = k. Hence the result is true for all n [greater than or equal to] 1.

Case (ii): (Regular graph of degree 2)

We have 6 = 2 + 2 + 2. Then this partition gives us a regular graph of degree 2 as shown in figure- (1.2). Suppose, there exist a regular graph of degree 2 for n = k in the graphical partitions of the number (2n + 4).

Then 2k + 4 = 2(k + 2) = 2 + 2 + 2 +...+ 2. =(k + 2) times of 2. If we introduce a new vertex in any one edge of the graph of the above partition then it will also be a regular graph of degree 2,which represent the graph of the partition 2 + 2 + 2 + .... to (k + 3) times of the number 2(k+3) i.e.{2(k+1)+4}. Hence the result is true for n=k+1 when it is true for n = k. Thus, the result is true for all n [greater than or equal to] 1

Theorem (2.2): The partition of the number [a.sub.n] = 4(n + 1), for n [greater than or equal to] 1 always contain one binary tree among all graphical tree partitions.

Proof: For n = 1, [a.sub.1] = 8.Then the partition 3 + 2 + 1 + 1 + 1 of 8 gives us a binary tree as shown in figure (2.1).

[FIGURE 2.1 OMITTED]

[FIGURE 2.2 OMITTED]

Let, the result is true for n = k, that is the partition of the number [a.sub.k] = 4(k+1), k [greater than or equal to] 1 always contain a binary tree among all graphical tree partitions. If we add two new vertices with any one vertex having degree 1,and another two new vertices with another vertex of degree 1 as shown in figure (2.2), then the new graph will also be a binary tree which represent the graphical partition of the number [a.sub.k + 1] = 4{(k + 1) + 1}. Thus the result is true for n = k + 1 when it is true for n = k. Hence the result is true for all n [greater than or equal to] 1.

Theorem (2.3): The graphical partition of the number [a.sub.n] = (n + 1)(n + 2) for n [greater than or equal to] 1 always contain one complete graph, which is regular also, having (n + 2) vertices with degree (n + 1) of each.

Proof: For n = 6 = 2 + 2 + 2, then the partition 2 + 2 + 2 of 6 represents a graph as shown in figure (1.2). Clearly, this graph is a complete graph as well as regular having vertices 1 + 2 = 3 of degree 2 Let the result is true for n = k, that is the graphical partitions of the number [a.sub.k] = (k + 1)(k + 2) always contain one complete graph which is regular also having (k + 2) vertices with degree (k + 1) of each. Now, if we introduce a new vertex by joining each of the (k + 2) vertices, then the resulting graph will also be a complete graph which is also regular of degree (k + 1) + 1 i.e. (k + 2) having (k + 2) + 1 i.e. (k + 3) vertices as shown in figure (3.1). Thus the result is true for n = k + 1 when it is true for n = k.

[FIGURE 3.1 OMITTED]

Theorem (2.4): In the partition of the number [a.sub.n] = 6n + 2, for n [greater than or equal to] 1 there always exists only one graphical tree partition whose structure satisfies the saturated hydrocarbon [C.sub.n][H.sub.2n + 2] for any given n-carbon atom. But there does not exist such type of chemical structure for the partitions of other numbers.

Proof: For n = 1, a1 = 8 = 4 + 1 + 1 + 1 + 1,this represent a graph which have one 4-degree vertex and four 1-degree vertices as shown in figure (4.1)

[FIGURE 4.1 OMITTED]

[FIGURE 4.2 OMITTED]

Let the result is true for n = k Then there exists k-vertices having degree 4 and the other vertices are of degree 1. If we add three new vertices with any one vertex of degree 1 as shown in figure (4.2), then the resulting graph have (k + 1) vertices of degree 4 and the others are of degree 1.This new graph is represented by the partition of the number [a.sub.k + 1] = 6(k + 1) + 2. Thus the result is true for n = k + 1 also when it is true for n = k. Hence, the result is true for all n [greater than or equal to] 1.

Algorithm

Input: Let (2n + 4)/(4n + 4)/(n + 1)(n + 2)/(6n + 2) for n [greater than or equal to] 1 be different types of even numbers.

Output: Find the various form of graphs obtained from the graphical parts g(2n + 4)/g(4n + 4)/g((n + 1)(n + 2))/g(6n + 2) of the partitions

p(2n + 4)/p(4n + 4)/p((n + 1)(n + 2))/p(6n + 2).

The following steps are considered.

Step-1: Study the graphical parts g (2n + 4)/g (4n + 4)/g ((n + 1) (n + 2))/g(6n + 2) of the partitions (2n + 4), (4n + 4), (n + 1) (n + 2), (6n + 2) for n [greater than or equal to] 1.

Step-2: If the [summation]d([v.sub.i]) = 2e, where d([v.sub.i]) is the degree of [v.sub.i] of the graphical parts g(2n + 4) for n [greater than or equal to] 1 and e [greater than or equal to] 3, then go to step-3 otherwise go to step-4.

Step-3: The graphical part is a regular graph of degree 1 or a graph of degree 2.

Step-4: If the [summation] d([v.sub.i]) = 2e, where d ([v.sub.i])is the degree of [v.sub.i] of the graphical part g(4n + 4) for n [greater than or equal to] 1 and e [greater than or equal to] 2r, r [greater than or equal to] 2, then go to step-5, otherwise go to step-6.

Step-5: The graphical part is a binary tree with leaf of the binary tree [greater than or equal to] 3, for simultaneous changes of r [greater than or equal to] 2 and n [greater than or equal to] 1.

Step-6:If the [summation]d([v.sub.i]) = 2e, where d([v.sub.i])is the degree of [v.sub.i] of the graphical part g((n + 1)(n + 2)) for n [greater than or equal to] 1 and e= (n + 1)(n + 2)/2, then go to step-7 otherwise go to step-8.

Step-7: The graphical part is a complete graph.

Step-8: If the [summation]d([v.sub.i]) = 2e, where d([v.sub.i])is the degree of [v.sub.i] of the graphical part g(6n + 2) for n [greater than or equal to] 1 and e=3n + 1 and maximum degree 4 , then go to step-9 and step-10.

Step-9: The graphical part is a graph of the form of saturated hydrocarbon [C.sub.n][H.sub.2n + 2] for given n-carbon atom, where n [greater than or equal to] 1.

Step-10: Stop.

Discussion

In our investigation the existence of at least two regular graphs of degree 1 and 2 are established for the numbers (2n + 4), where n [greater than or equal to] 1, admitting graphical partitions. Further in graphical tree partitions of the numbers [a.sub.n] = 4(n + 1), n [greater than or equal to] 1, each partition is found to contain a binary tree. Interestingly, a complete but regular graph of (n + 2) vertices, each of degree (n + 1) is established to exist for the graphical partitions of the numbers [a.sub.n] = (n + 1)(n + 2) where n [greater than or equal to] 1.It is noteworthy to mention that in our investigation, the partition of the numbers [a.sub.n] = 6n + 2, for n [greater than or equal to] 1. One graphical tree partition satisfying saturated hydro-carbon [C.sub.n][H.sub.2n + 2] for any given n-carbon atom has been established. This is really a new light in this direction. Finally, we put forward a column of algorithms for verification of our reported results.

References

 Bressound, D.: Extension of the partition Sieve J. Number Th.12, 87-100 (1980).

 B. Pittel, confirming two conjectures about the integer partitions. J. Combinatorial Theory series A, 88, no. 1 (1999), 123-135.

 C.C. Rousseau and F. Ali, on a conjecture concerning graphical partitions, congr. Number. 104 (1994), 150-160. , A note on graphical partitions, Journal of Combinatorial Theory series B, 64 (1995), 314-318.

 Deborah A. Frank, Carla D. Savage and James A. Sellers, "On The number of Graphical Forest Partititions". 

 Douglas B. West, "Introduction to Graph Theory", 2nd edition, Prentice Hall, 2003.

 Erdos, P., Richmond, L.: On graphical partitions. Combinatorica 13(1), 57-63 (1993).

 Erdos, P Gallai, T.: Graphs with prescribe degrees of vertices (Hungarian). Mat.Lapok 11 (1960).264-274.

 Harary, F. Graph Theory. Addition-Wesley 1971.

 J.M. Nolan, V. Sivaraman, C.D. Savage, and P.k. Tiwari, Graphical Basis partitions, Graphs and combinatorics, 14,no.3 (1998), 241-261.

 Macdonald, I.G., "Symmetric Functions and Hall Polynomials, 2nd edition", oxford sci. publ., Oxford Univ. Press, London OX2 6DP, 1995.

 Roth, F.F, Szekeres: Some asymptotic formulas in the theory of partitions. Quart.J. Math. Oxford ser. (2) 5, 241-259 (1954).

(1) Banamali Nath, (2) Bichitra Kalita and (3) Bhaben ch. Kalita

(1) Department of Mathematics, Chhaygaon College, Chhaygaon, Kamrup (Assam), Pin-781124.

(2) Dept of Computer Application (M.C.A), Assam Engg. College, Guwahati-781013, Assam,

(3) Department of Mathematics, Gauhati University, Guwahati-781014