Main Article Content
Abstract
A split graph is a graph in which the vertices can be partitioned into an independent set and a clique. A graph is split if and only if it has no induced subgraph isomorphic to C5, C4 or 2K2, which is a well-known characterization for split graph. A property of a graph G is recognizable if it can be recognized from the collection of all maximal proper induced subgraphs of G. We show that any nonsplit graph can have at most five split maximal induced subgraphs. Also we list out all C5-free nonsplit graphs having split maximal induced subgraphs, which is the main and, in fact, tedious result of this paper
Keywords
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
References
- K. J. Asciak, M. A. Francalanza, J. Lauri, and W. Myrvold, A survey of some open questions in reconstruction numbers, Ars Combin. 97 (2010), 443 –456.
- B. Bollobas, Almost every graph has reconstruction number three, J. Graph Theory 14 (1) (1990), 1 – 4.
- F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, 1990.
- J. A. Bondy, A graph reconstructor’s manual, in Surveys in Combinatorics (Proceedings of British Combinatorial Conference), London Mathematical Society Lecture Notes. 116 (1991), 221 –252.
- P. Devi Priya and S. Monikandan, Reconstruction of distance hereditary 2-connected graphs, Discrete Math. 341 (2018), 2326 - 2331.
- S. Foldes and P. L. Hammer, Split graphs, University of Waterloo, CORR 76-3, March 1976.
- S. Foldes and P. L. Hammer (1977b), Split graphs having Dilworth number two, Canad. J. Math., 29 (3), 666 – 672.
- F. Harary, On the reconstruction of a graph from a collection of subgraphs, Theory of graphs and its applications (M. Fieldler Ed.) Academic Press, New York (1964), 47 – 52.
- F. Harary and M. Plantholt, The graph reconstruction number, J. Graph Theory 9 (1985), 451 – 454.
- N. Kalai Mathi and S. Monikandan (2020) Degree associated edge reconstruction number of split graphs with biregular independent set is one, AKCE Int. J. Graphs Comb., published online on April 2020. https://DOI:10.1016/j.akcej.2019.12.009
- J. Lauri, Vertex deleted and edge deleted subgraphs, Collected papers published on the occasion of the Quatercentenary Celebrations, University of Malta (1993), 495 – 524.
- R. Merris, Split graphs, European J. Combin. 24 (2003), 413 –430.
- R. Molina, Correction of a proof on the ally-reconstruction number of a disconnected graph, Ars Combin. 40 (1995), 59 – 64.
- S. Monikandan and A. Anu. Reconstruction Number of connected graphs with unique pendant vertex, Discrete Applied Mathematics, Published online on June, 2020. https://doi.org/10.1016/j.dam.2020.06.005
- W. J. Myrvold, The ally and adversary reconstruction problems, Ph.D. Thesis, University of Waterloo, 1988.
- W. J. Myrvold, A report on the ally reconstruction problem, Graph Theory, Combinatorics and Application (Edited by Y. Alavi, G. Chartrand, O. R. Oellermann and A. J. Schwenk) 2 (1988),947 – 956.
- D. Rivshin and S. P. Radziszowski, The vertex and edge graph reconstruction numbers of small graphs, Australas. J. Combin. 45 (2009), 175 – 188.
- R. Merris, Graph Theory, Wiley Interscience, New York, 2001.
- P.L. Hammer, B. Simeone, The splittance of a graph, Combinatorica 1 (1981), 275284.
- D. B. West, Introduction to graph theory, Prentice-Hall, Second edition, 2005.
- Y. Yongzhi, The reconstruction conjecture is true if all 2-connected graphs are reconstructible, J. Graph Theory 12 (2) (1988), 237 – 243.
References
K. J. Asciak, M. A. Francalanza, J. Lauri, and W. Myrvold, A survey of some open questions in reconstruction numbers, Ars Combin. 97 (2010), 443 –456.
B. Bollobas, Almost every graph has reconstruction number three, J. Graph Theory 14 (1) (1990), 1 – 4.
F. Buckley and F. Harary, Distance in Graphs, Addison-Wesley, 1990.
J. A. Bondy, A graph reconstructor’s manual, in Surveys in Combinatorics (Proceedings of British Combinatorial Conference), London Mathematical Society Lecture Notes. 116 (1991), 221 –252.
P. Devi Priya and S. Monikandan, Reconstruction of distance hereditary 2-connected graphs, Discrete Math. 341 (2018), 2326 - 2331.
S. Foldes and P. L. Hammer, Split graphs, University of Waterloo, CORR 76-3, March 1976.
S. Foldes and P. L. Hammer (1977b), Split graphs having Dilworth number two, Canad. J. Math., 29 (3), 666 – 672.
F. Harary, On the reconstruction of a graph from a collection of subgraphs, Theory of graphs and its applications (M. Fieldler Ed.) Academic Press, New York (1964), 47 – 52.
F. Harary and M. Plantholt, The graph reconstruction number, J. Graph Theory 9 (1985), 451 – 454.
N. Kalai Mathi and S. Monikandan (2020) Degree associated edge reconstruction number of split graphs with biregular independent set is one, AKCE Int. J. Graphs Comb., published online on April 2020. https://DOI:10.1016/j.akcej.2019.12.009
J. Lauri, Vertex deleted and edge deleted subgraphs, Collected papers published on the occasion of the Quatercentenary Celebrations, University of Malta (1993), 495 – 524.
R. Merris, Split graphs, European J. Combin. 24 (2003), 413 –430.
R. Molina, Correction of a proof on the ally-reconstruction number of a disconnected graph, Ars Combin. 40 (1995), 59 – 64.
S. Monikandan and A. Anu. Reconstruction Number of connected graphs with unique pendant vertex, Discrete Applied Mathematics, Published online on June, 2020. https://doi.org/10.1016/j.dam.2020.06.005
W. J. Myrvold, The ally and adversary reconstruction problems, Ph.D. Thesis, University of Waterloo, 1988.
W. J. Myrvold, A report on the ally reconstruction problem, Graph Theory, Combinatorics and Application (Edited by Y. Alavi, G. Chartrand, O. R. Oellermann and A. J. Schwenk) 2 (1988),947 – 956.
D. Rivshin and S. P. Radziszowski, The vertex and edge graph reconstruction numbers of small graphs, Australas. J. Combin. 45 (2009), 175 – 188.
R. Merris, Graph Theory, Wiley Interscience, New York, 2001.
P.L. Hammer, B. Simeone, The splittance of a graph, Combinatorica 1 (1981), 275284.
D. B. West, Introduction to graph theory, Prentice-Hall, Second edition, 2005.
Y. Yongzhi, The reconstruction conjecture is true if all 2-connected graphs are reconstructible, J. Graph Theory 12 (2) (1988), 237 – 243.