Counting the Number of Disconnected Labeled Graphs of Order Five without Paralel Edges

Wamiliana Wamiliana, Amanto Amanto, Grita Tumpi Nagari

Abstract


Abstract— Given a graph G(V,E) with n vertices and m edges, where every vertex is labeled, there are a lot of possible graphs that can be constructed, either connected graphs or disconnected, simple or not simple. A graph G(V,E) is called as a connected graph if there exists at least one path between every pair of vertices in G, and otherwise, G is disconnected. A graph G is called as a labeled graph if every node/vertex and or every edge is labeled. In this research, we are concerning about a graph where every vertex is labeled. Parallel edges are two edges or more which have the same end points. In this research we found that the number of disconnected labeled graph without parallel edges for  and  can be obtained with the following formula:

 {{.    is the number of disconnected labeled graph without parallel edges for  and .

 

Keywords—  counting graph, labeled graph, disconnected, parallel edges


Full Text:

PDF

References


Foulds, L.R. Graph Theory Applications. Springer-Verlag, New

York, USA, 1992.

Hsu, L.H., and Lin, C.K. Graph Theory and interconnection

network. Taylor and Francis Group, LLC, New York, 2009.

Cayley, A., ‘On the Mathematical Theory of Isomers’,

Philosophical Magazine, vol. 47, no. 4, 1874, pp.444 - 446 ,

Slomenski, W.F.(1964), ‘Application of the Theory of Graph to

Calculations of the Additive Structural Properties of Hydrocarbon’,

Russian Journal of Physical Chemistry, vol. 38, 1964, pp.700-703

Harary F, and E. M. Palmer, Graphical Enumeration. Academic

Press, New York, 1973

Stanley, R.P ,. Enumerative Combinatorics, Vol. 1, number 49 of

Cambridge Studies in Advanced Mathematics. Cambridge University

Press, New York. 1997

Stanley, R.P , Enumerative Combinatorics, Vol. 2, number 62 of

Cambridge Studies in Advanced Mathematics. Cambridge University

Press, New York, 1999.

[ Wilf, H, 1. Generating Functionology. Academic Press, second

Edition, New York, 1994

Agnarsson, G. and , R.D.Greenlaw, Graph Theory Modelling,

Application,and Algorithms. Pearson/Prentice Education, Inc., New

Jersey.




DOI: http://dx.doi.org/10.23960/ins.v1i1.7

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
View My Stats
Flag Counter