Vulnerability of super connected split graphs and bisplit graphs

Litao Guo; Bernard L. S. Lin

doi:10.3934/dcdss.2019081

Article Contents

2019, Volume 12, Issue 4&5: 1179-1185. Doi: 10.3934/dcdss.2019081 open access

This issue Previous Article Three-dimensional computer simulation of twill woven fabric by using polynomial mathematical model Next Article Cores and optimal fuzzy communication structures of fuzzy games

Vulnerability of super connected split graphs and bisplit graphs

Litao Guo^1, and
Bernard L. S. Lin^2, ,

1.
School of Applied Mathematics, Xiamen University of Technology, Xiamen, Fujian 361024, China
2.
School of Science, Jimei University, Xiamen, Fujian 361021, China

* Corresponding author: Bernard L. S. Lin
* Corresponding author: Bernard L. S. Lin

Received: June 30, 2017

Revised: December 31, 2017

Published: March 2019

Abstract Full Text(HTML) Figure(4) Related Papers Cited by

Abstract

A graph $G = (C, I, E)$ is called a split graph if its vertex set $V$ can be partitioned into a clique $C$ and an independent set $I$. A graph $G = (Y \cup Z, I, E)$ is called a bisplit graph if its vertex set $V$ can be partitioned into three stable sets $I, Y,Z$ such that $Y \cup Z$ induces a complete bipartite graph and an independent set $I$. A connected graph $G$ is called supper-$κ$ (resp. super-$λ$) if every minimum vertex cut (edge cut) of $G$ is the set of neighbors of some vertex (the edges of incident to some vertex) in $G$. In this note, we show that: split graphs and bisplit graphs are super-$κ$ and super-$λ$.

Keywords:

Mathematics Subject Classification: Primary: 05C40; Secondary: 05C90.

Citation:

FullText(HTML)

Figure 1. $G$ is not super-$\kappa$

Download: Full-size image PowerPoint slide

Figure 2. $G$ is not super-$\lambda$

Download: Full-size image PowerPoint slide

Figure 3. $G$ is not super-$\lambda$

Download: Full-size image PowerPoint slide

Figure 4. shuttle graph

Download: Full-size image PowerPoint slide

Related Papers

Cited by

References

[1]	J. A. Bondy and U. S. R. Murty, Graph Theory and Its Application, Academic Press, New York, 1976.
[2]	A. Brandstät, P. L. Hammer, V. B. Le and V. V. Lozin, Bisplit graphs, Discrete Math., 299 (2005), 11-32. doi: 10.1016/j.disc.2004.08.046.
[3]	S. Födes and P. L. Hammer, Split graphs, Congr. Numer., 1 (1977), 311-315.
[4]	L. T. Guo, C. Qin and X. F. Guo, Super connectivity of Kronecker products of graphs, Information Processing Letters, 110 (2010), 659-661. doi: 10.1016/j.ipl.2010.05.013.
[5]	L. T. Guo, W. Yang and X., F. Guo, Super-connectivity of Kronecker products of split graphs, powers of cycles, powers of paths and complete graphs, Applied Mathematics Letters, 26 (2013), 120-123. doi: 10.1016/j.aml.2012.04.006.
[6]	M. Metsidik and E. Vumar, Edge vulnerability parameters of bisplit graphs, Computers and Mathematics with Applications, 56 (2008), 1741-1747. doi: 10.1016/j.camwa.2008.04.015.
[7]	G. J. Woeginger, The toughness of split graphs, Discrete Math., 190 (1998), 295-297. doi: 10.1016/S0012-365X(98)00156-3.
[8]	S. Zhang, Q. Zhang and H. Yang, Vulnerability parameters of split graphs, Int. J. Comput. Math., 85 (2008), 19-23. doi: 10.1080/00207160701365721.
[9]	Q. Zhang and S. Zhang, Edge vulnerability parameters of split graphs, Applied Mathematics Letters, 19 (2006), 916-920. doi: 10.1016/j.aml.2005.09.011.