Diameter and Travers ability of PAN Critical
Graphs

J. Suresh Kumar

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

International Journal of Mathematics Trends and Technology

Research Article | Open Access | Download PDF

Volume 52 | Number 7 | Year 2017 | Article Id. IJMTT-V52P564 | DOI : https://doi.org/10.14445/22315373/IJMTT-V52P564

Diameter and Travers ability of PAN Critical Graphs

J. Suresh Kumar

Citation :

J. Suresh Kumar, "Diameter and Travers ability of PAN Critical Graphs," International Journal of Mathematics Trends and Technology (IJMTT), vol. 52, no. 7, pp. 449-451, 2017. Crossref, https://doi.org/10.14445/22315373/IJMTT-V52P564

Abstract

A pseudo-complete coloring of a graph G is an assignment of colors to the vertices of G such that for any two distinct colors, there existadjacent vertices having those colors. The maximum number of colors used in a pseudocomplete coloring of G is called the pseudoachromatic number of G and is denoted by𝜓𝑠(𝐺). A graph G is called edge critical if 𝜓𝑠(𝐺 − 𝑒)<𝜓𝑠 (𝐺)for any edge e of G. A graph G is called vertex critical if 𝜓𝑠 𝐺 − 𝑣 <. 𝜓𝑠(𝐺)for every vertex v of G. These graphs are generally called as pseudoachromatic number critical graphs (shortly as PAN Critical graphs). In this paper, we investigate the properties of these critical graphs.

Keywords

Pseudo-complete coloring, Pseudoachromatic number, k-edge critical graph, kvertex critical graph.

References

[1] G. A. Dirac, Some theorems on abstract graphs, Proc. London Math. Soc. 2 (3) (1952), 69-81.
[2] G. A. Dirac, A property of 4-chromatic graphs and some remarks on critical graphs, J. London Math. Soc. 27 (1952), 85-92.
[3] F. Harary, S. Hedetniemi and G. Prins, An Interpolation theorem for graphical homomorphisms, Portugal Math. 26 (1967), 453-462.
[4] F. Harary and S. Hedetniemi, Achromatic number of a graph, J. Comb. Theory 8 (1970), 154-161.
[5] R. P. Gupta, Bounds on the chromatic and achromatic numbers of complementary graphs, Recent Progress in Combinatorics, Ed. W. T. Tutte, Academic Press, New York (1969).
[6] E. Sampathkumar and V. N. Bhave, Partition graphs and coloring numbers of a graph, Discrete Math. 16 (1976), 57-60.
[7] J. Suresh Kumar, On Pseudo-complete colorings and Graphoidal colorings of a graph, Ph.D. Thesis, M.S. University, Thirunelveli, Tamilnadu, India, June, 2002.
[8] F. Harary, Graph Theory, Reading Mass, 1969.