RELATIONSHIP BETWEENCOLORING,EMBEDDINGAND DECYCLING NUMBER OF A GRAPH

admin August 21, 2020

Authors:

Sajid Hussain, Ren Han,Nisar Hussain Khoja,

DOI NO:

https://doi.org/10.26782/jmcms.2020.08.00011

Keywords:

Decycling number,Chromatic number,Maximum degree,Embedding,Girth,hypercube,

Abstract

A set  of vertices of a graph  is said to be a decycling set if  is acyclic. The size of a minimum decycling set of  is called the decycling number of  and it is denoted by In this paper, our chief objectives areto obtain the upper bound of the decycling number of a graph by using graph chromatics number and its order. The relation of the genus of the surface  and the decycling number of a graph embedded in surface  is studied. The decycling number of a planar graph with  vertices is conjectured to be , which is shown in this paper if the girth of the graph is at least four. The decycling number of a graph with  vertices and maximum degree three is proved to be at most Also, we completely investigatethe decycling number of the hypercube .

Refference:

I Albertson M and Berman D., The acyclic chromatic number, Congr. Number., 17(1976),51-69.
II BauS and Beineke L., The decycling number of graphs, Australas J. Combin., 25(2002),285-298.
III Beineke L and Vandell R., Decycling graphs, J.Graph Theory, 25(1997), No.1:59-77.
IV Beineke L and Harary F., The genus of the n-cube, Canad. J.Math.17(1965),494-496.
V Bondy J.A and Murty U.S.R., Graph Theory, Springer, 2008.
VI Brooks R.L, on coloring the nodes of a network, Proc. Cambridge Philos. Soc.37(1941),194-197.
VII Chartrand G, Kronk H.V and Wall C.E., The point-arboricity of a graph, Israel J. Math. (1968) 6:169C175.
VIII ErdÖs P, Saks M and Sós V, Maximum induced trees in graphs, J. Combin. Theory Ser.B,41(1986),61-79.
IX Festa P,Pardalos P.M and Reseude M.G.C., Feedback set problem, in Handbook ofCombinatorial Optimization, Supplement Vol. A Kluwer, Dordrecht, (1999),209-258.
X Heahood P.J., Map-colour theorem, Quart. J.Pure Appl.Math.24(1890),332-338.
XI Karp R.M, Miller R.E., and Thatcher J.M., Reducibility among combinatorial problems. J.Symb. Log.40(1975):618C619.
XII Kirchhoff K, Über die Auflösung der Gleichungen, auf welche man bei derUntersuchung der linearen VerteilunggalvanischerStrömeGfϋhrtwird, Ann.Phy. Chem, 72 (1847) 497-508.
XIII Liu J.P and Zhao C, A new bound on the feedback vertex sets in cubic graphs, Discrete Math., 184(1996), 119-131.
XIV Long S.D., Ren H, The decycling number and maximum genus of cubic graphs, Journal of GraphTheory, 88 (2018),375 C384.
XV Pike D.A, Decycling hypercubes, Graphs and Combin., 19(2003),547-550.

XVI Pike D.A and Zou Y., Decycling cartesian products of two cycles, SIAM J. Discrete Math. 19(2005),No. 3:651-663.
XVII Punnim N, Decycling connected regular graphs, Austral. J. Combin., 35(2006), 155 169.
XVIII Punnim N, The decycling number of regular graphs, Thai J. Math.,4(2006),145-161.
XIX Ren H, Yang C., and T.X Zhao, A new formula for the decycling number of regular graphs, DiscreteMath. 340(2017),3020-3031.
XX Thomassen C, Five-coloring maps on surfaces, J.Combin. Theory Ser.B,59(1993),89-105.
XXI White A.T, Graphs of groups on surfaces, Elsevier, Amsterdam, London, New York, Oxford, Paris, Shannon, Tokyo, 2001.
XXII Wilson R.J, Introduction to graph theory 4th Ed., Addison –Wesley Longman, Reading MA. (1996).
XXIII Zheng M and Lu X, On the maximum induced forests of a connected cubic graph without triangles, Discrete Math.,85(1990), 89-96.

View Download