Main Article Content
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
Article Details
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.
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.