Low and High Vertices in Edge Critical Graphs

Dr. J. Suresh Kumar

doi:https://doi.org/10.14445/22315373/IJMTT-V65I4P507

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 65 | Issue 4 | Year 2019 | Article Id. IJMTT-V65I4P507 | DOI : https://doi.org/10.14445/22315373/IJMTT-V65I4P507

Low and High Vertices in Edge Critical Graphs

Dr. J. Suresh Kumar

Abstract

If a graph G is k-edge critical, then its maximum degree is at most k-1. Motivated from this result, we define a vertex of a k-edge critical graph as a high vertex, if its degree is k-1 and as a low vertex, otherwise. In this Paper, we investigate the properties of the low and high vertices and the subgraphs induced by the sets of low or high vertices of a k-edge critical graph.

Keywords

k-edge critical graph, Chromatic number, High vertex.

References

[1] Dirac G.A., Some theorems on abstract graphs, Proc. London Math. Soc.,2, (3) (1952), 69-8 1.
[2] Dirac G.A., A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc., 27, (1952), 85-92.
[3] Gallai T., Kritische Graphen I , Magyar Tud A/cad. Mat. Kutato. mt. K6 z1 ,8, (1963), 165-192.
[4] Gallai 1., Kritische Graphen II, Magyar Tud Akad. Mat. Kutato. mt. K6 z1 ,8, (1963), 373-395.
[5] Sachs H., On colour critical graphs, Fundamentals of Computation theory, FCT '85. Cottbus, GDR, Sept. 1985. Lecture notes in Computer Science, Springer Verlag, (1985), 390-401.
[6] Sachs H. and M.Stiebitz, Construction of. colour-critical graphs with given major-vertex subgraph, Combinatorial Mathematics, Annals .of Discrete Math., 17, (1983), 581- 598.
[7] Stiebitz M., Beitrrrrge zur theorie der farbungs kritischen graphen, Dissertationsschrfl (B), Technische Hochschule Ilmenau (1985).
[8] SureshKumar J and D Satheesh E.N, Pseudo-Complete Color Critical Graphs, International Journal for Research in Applied Science & Engineering Technology (IJRASET) Volume 6, Issue I, January 2018.
[9] Suresh Kumar J, Degrees and Degree Sequences of PAN Critical Graphs, International Journal for Mathematics And its Applications (IJMAA), 6(1–B)(2018).
[10] Suresh Kumar J, Diameter and Traversability of PAN Critical Graphs International Journal of Mathematics Trends and Technology (IJMTT), Volume.52, Number 7, December 2017.
[11] Suresh Kumar J, On Pseudo-Complete Colorings and Graphoidal colorings of a graph, Ph.D. Thesis, M.S. University, Thirunelveli, Tamilnadu, India, 2002.

Citation :

Dr. J. Suresh Kumar, "Low and High Vertices in Edge Critical Graphs," International Journal of Mathematics Trends and Technology (IJMTT), vol. 65, no. 4, pp. 36-38, 2019. Crossref, https://doi.org/10.14445/22315373/IJMTT-V65I4P507