August & September  2019, 12(4&5): 1179-1185. doi: 10.3934/dcdss.2019081

Vulnerability of super connected split graphs and bisplit graphs

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

Received  July 2017 Revised  January 2018 Published  November 2018

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-$λ$.

Citation: Litao Guo, Bernard L. S. Lin. Vulnerability of super connected split graphs and bisplit graphs. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1179-1185. doi: 10.3934/dcdss.2019081
References:
[1]

J. A. Bondy and U. S. R. Murty, Graph Theory and Its Application, Academic Press, New York, 1976.  Google Scholar

[2]

A. BrandstätP. L. HammerV. B. Le and V. V. Lozin, Bisplit graphs, Discrete Math., 299 (2005), 11-32.  doi: 10.1016/j.disc.2004.08.046.  Google Scholar

[3]

S. Födes and P. L. Hammer, Split graphs, Congr. Numer., 1 (1977), 311-315.   Google Scholar

[4]

L. T. GuoC. 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.  Google Scholar

[5]

L. T. GuoW. 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.  Google Scholar

[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.  Google Scholar

[7]

G. J. Woeginger, The toughness of split graphs, Discrete Math., 190 (1998), 295-297.  doi: 10.1016/S0012-365X(98)00156-3.  Google Scholar

[8]

S. ZhangQ. Zhang and H. Yang, Vulnerability parameters of split graphs, Int. J. Comput. Math., 85 (2008), 19-23.  doi: 10.1080/00207160701365721.  Google Scholar

[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.  Google Scholar

show all references

References:
[1]

J. A. Bondy and U. S. R. Murty, Graph Theory and Its Application, Academic Press, New York, 1976.  Google Scholar

[2]

A. BrandstätP. L. HammerV. B. Le and V. V. Lozin, Bisplit graphs, Discrete Math., 299 (2005), 11-32.  doi: 10.1016/j.disc.2004.08.046.  Google Scholar

[3]

S. Födes and P. L. Hammer, Split graphs, Congr. Numer., 1 (1977), 311-315.   Google Scholar

[4]

L. T. GuoC. 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.  Google Scholar

[5]

L. T. GuoW. 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.  Google Scholar

[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.  Google Scholar

[7]

G. J. Woeginger, The toughness of split graphs, Discrete Math., 190 (1998), 295-297.  doi: 10.1016/S0012-365X(98)00156-3.  Google Scholar

[8]

S. ZhangQ. Zhang and H. Yang, Vulnerability parameters of split graphs, Int. J. Comput. Math., 85 (2008), 19-23.  doi: 10.1080/00207160701365721.  Google Scholar

[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.  Google Scholar

Figure 1.  $G$ is not super-$\kappa$
Figure 2.  $G$ is not super-$\lambda$
Figure 3.  $G$ is not super-$\lambda$
Figure 4.  shuttle graph
[1]

Shipra Singh, Aviv Gibali, Xiaolong Qin. Cooperation in traffic network problems via evolutionary split variational inequalities. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020170

2019 Impact Factor: 1.233

Metrics

  • PDF downloads (68)
  • HTML views (390)
  • Cited by (0)

Other articles
by authors

[Back to Top]