The Eigen-chromatic Ratio of Classes of Graphs: Asymptotes, Areas and Molecular Stability

Paul August Winter; Roger Mbongo Mayala; Proscovia Namayanja

Paul August Winter Senior research associate, Department of Mathematics in the School of Mathematics, Statistics and Computer Science, University of Kwazulu-Natal, South Africa http://orcid.org/0000-0003-3539-7047
Roger Mbongo Mayala Post Graduate scholar, Department of Mathematics, University of KwaZulu-Natal, Durban, South Africa
Proscovia Namayanja Mathematics Lecturer, Department of Mathematics, University of KwaZulu-Natal, Durban, South Africa

Keywords: Eigenvalue, Energy of graph, Chromatic number, Ratio, Asymptote, Area.

Abstract

In this paper, we present a new ratio associated with classes of graphs, called the eigen-chromatic ratio, by combining the two graph theoretical concepts of energy and chromatic number.

The energy of a graph, the sum of the absolute values of the eigenvalues of the adjacency matrix of a graph, arose historically as a result of the energy of the benzene ring being identical to that of the sum of the absolute values of the eigenvalues of the adjacency matrix of the cycle graph on n vertices (see [18]).

The chromatic number of a graph is the smallest number of colour classes that we can partition the vertices of a graph such that each edge of the graph has ends that do not belong to the same colour class, and applications to the real world abound (see [30]). Applying this idea to molecular graph theory, for example, the water molecule would have its two hydrogen atoms coloured with the same colour different to that of the oxygen molecule.

Ratios involving graph theoretical concepts form a large subset of graph theoretical research (see [3], [16], [48]). The eigen-chromatic ratio of a class of graph provides a form of energy distribution among the colour classes determined by the chromatic number of such a class of graphs. The asymptote associated with this eigen-chromatic ratio allows for the behavioural analysis in terms of stability of molecules in molecular graph theory where a large number of atoms are involved.

This asymptote can be associated with the concept of graphs being hyper- or hypo- energetic (see [48]).

Downloads

Download data is not yet available.

References

F. J. Adewusi (2014). Spanning Trees: Eigenvalues, Special Numbers, and the Tree-Cover Ratios, Asymptotes and Areas of Graphs, M. Sc. Dissertation, University of KwaZulu-Natal.

C. Agida, A. Bayad, I. Gustman and S.A. srinivas (2012). The minimum covering energy of a graph. Kragujevac J. Sci. 34, 39-56.

N. Alon, Eigenvalues and expanders (1986). Combinatoric 6, 83-96.

N. Alon and J. H. Spencer, Eigenvalues and Expanders (2011). The Probabilistic Method (3rd ed.), John Wiley & Sons.

T. Ando (1987).Totally positive matrices: Linear Algebra and its applications, 90.

H. Anton (1977). Elementary Linear Algebra, John Wiley and Sons, Inc.

C. J. Ballhausen and H. B. Gray (1964). Molecular-Orbital Theory, Benjamin, New York.

G. Bacak (2004). Vertex Coloring of Graph, M.Sc. Dissertation, Izmir Institute of Technology.

L. W. Beineke, R. J. Wilson and P. J. Cameron (2007). Topics in Algebraic Theory, Cambridge, University Press.

K. A. Berman and J. L. Paul (1997). Fundamentals of Sequential and Parallel Algorithms, PWS, Publishing Company.

H. Q. Bian (2008). Isomorphic Lollipop Graphs are cospectral with respect to the adjacency. Int. J. Contemp. Math. sciences, Vol. 3, no.36, 1783-1788.

J. M. Boyer and W. J. Myrvold (2004). On the cutting edge: Simplified O(n) planarity by edge addition, Journal of Graph Algorithms and Application, 8(2):241-273.

A. E. Brouwer and W. H. Haemers (2011). Spectra of Graphs, Springer, New York.

A. E. Brouwer and W. H. Haemers (2012). Distance of regular graphs, Springer, New York.

R. A. Brualdi (2006). Energy of graph, Notes to AIM Workshop on spectra of families of matrices described by graphs, digraphs and sign pattern.

F. Buckley (1982). The central ratio of a graph, Discrete Mathematics. 38(1): 17-21.

G. Chartrand (2006). Introduction to graph theory, Tata McGraw-Hill Education.

C. A. O. Coulson, B. Leary and R. B. Mallion (1978). Huckel Theory for Organic Chemists, Academic Press.

D. M. Cvetkovic and I. Gutman (2009). Application of graph spectra.

D. M. Cvetkovic, P. Rowlinson and S. Simic (2010). An introduction to the theory of graph spectra, Cambridge/ New-York.

S. Gabor (2006). Asymptotic values of the Hall-ratio for graph powers, Discrete Mathematics, 306(19-20): 2593-2601.

F. R. Gantmacher (1959). The Theory of Matrices, Chelsea.

C. Godsil and G. Royle (2004). Algebraic Graph Theory, New York: Springer-Verlag.

Harry B. Gray (1965). Electron and Chemical Bonding, W. A. Benjamin, INC, New York.

J. Gross and J. Yellen (1999). Graph Theory and Its Applications, CRC Press.

I. Gustman (1978). The Energy of Graph, 10.Steiermarkisches Mathematisches Symposium (Stift Rein, Graz, 1978), 103 1-22.

J. M. Harris, J. L. Hirst and M. Mossinghoff (2008). Combinatorics and Graph theory, Springer, New York.

G. Indual and A. Vijayakumar (2008). A note on energy of some graphs. Communications in Mathematical an in Computer Chemistry 59 269-274.

C. L. Jessop (2014). Matrices of Graphs and Designs with Emphasis on their Eigen-Pair Balanced Characteristic, M. Sc. Dissertation, University of KwaZulu-Natal.

E. L. Lawler (1976). A note on the complexity of the chromatic number Problem, Information Processing Letters, 5(3): 66-67.

S. L. Lee and Y. Yeh (1993). Eigenvalues and Eigenvectors of graphs, Journal of Mathematical Chemistry, Vol 12, 121-123.

V. Nikiforov (2002). Some Inequalities for the Largest Eigenvalues of Graph, J. Combinatorics, Probability and computing, Vol. 11 Issue 2, 179-189.

S. O. Ojako (2015). Energy of Graphs: The Eigen-Complete Difference Ratio With Its Asymptotic, Domination And Area Aspects, M. Sc. Dissertation, University of KwaZulu-Natal.

M. R. Rajesh Kanna and All (2016). Specific energies of Friendship Graph, Asian Academic Research Journal of Multidisciplinary, Vol.3 Issue 1, 2319-2801.

D. Stevanovic (2006). Energy of Graphs: A few open problems and some suggestions, dragance106@yahoo.com, University of Ni's, Serbia.

J. R. Vermette (1978). Special and Combinatorial Properties of Friendship Graphs, Simplicial Rook Graphs, and Extremal Expanders, ProQuest, 2015;

P. A. Winter (2014). The chromatic-complete difference ratio of graphs, Vixra 1503.0046 23.

P. A. Winter (2015). The Chromatic-Cover Ratio of a Graph: Energy Conservation, Domination, Areas and Farey Sequences, Journal of Science, 5(12): 1435-1443.

P. A. Winter (2015). Graph theory and calculus: ratios of classes of graphs, Lambert Academic Publishing Company, Germany.

P. A. Winter (2015). Tree-3-cover ratio of graphs: asymptotes and areas. viXra. 1503.0124. 18 pages.

P. A. Winter and F.J. Adewusi (2014). Tree-Cover Ratio of Graphs with Asymptotic Convergence Identical to The Secretary Problem, Advances in Mathematics: Scientific Journal, 3(2): 47-61.

P. A. Winter and C.L. Jessop (2014). Integral Eigen-Pair Balanced Classes of Graphs: Ratios, Asymptotes, Areas and Complementary Involution, International Journal of Combinatorics, Volume 2014, Article ID 148690, 16 pages.

P. A. Winter and C. L. Jessop (2015). The eigen-Cover Ratio of Graphs: Asymptotes, Domination and Areas. Global Journal of Mathematics. Volume 2, Issue 2, 37-47.

P. A. Winter, C. L. Jessop and F. J. Adewusi, The complete graph: Eigenvalues, trigonometrical unit-equations with associated t-complete-eigen sequences, ratios, sums and diagrams. To appear in Journal of Advances in Mathematics.

P. A. Winter and C. L. Jessop (2015). Analytical methods to obtain the Energy of graphs. Journal of Advances in Mathematics. Volume 3, Issue 1.

P. A. Winter and C. L. Jessop (2015). The Eigen-3-Cover Ratio of Graphs: Asymptotes, Domination and Areas. Global Journal of Mathematics. Volume 3, Issue 1.

P. A. Winter and C. L. Jessop (2015). The Laplacian Eigen-Cover Ratio of Graphs: Asymptotes, Domination and Areas. Global Journal of Mathematics. Volume 6, No.1.

P. A. Winter and C. L. Jessop (2016). Spectra of Graphs with End Vertices Appended to All Vertices of the Base Graph: The Golden Ratio and Energy. Academic Journal of Applied Mathematical Sciences. Volume 2, No: 7, pp: 56-69.

P. A. Winter and S. O. Ojako (2015). The Eigen-complete Difference Ratio of classes of Graphs: Domination, Asymptotes and Area, Journal of Advances in Mathematics, 10( 9): 3800-3811.

P. A. Winter and D. Sarvate (2014). The h-eigen energy formation number of h-decomposable classes of graphs: formation ratios, asymptotes and power, Advances in Mathematics: Scientific Journal, 3(2): 133-147.

W. J. Wiswesser (1954). A Line-formula Chemical Notation, Crowell: New York.

C. Woods (2013). My Application using graph Eigenvalues: Graph Energy.

D. G. Zill. A first course in differential equation, the classic first edition, Brooks/ Cole Pub Co;

D. Zill and W. Wright (2013), Differential equation and boundary value problems, Brooks/ Cole, Boston.