American Institute of Mathematical Sciences

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

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

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

Keywords: Split graphs, bisplit graphs, super connectivity, super edge connectivity.
Mathematics Subject Classification: Primary: 05C40; Secondary: 05C90.
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ä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.  Google Scholar

[3]

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

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

[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.  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. Zhang, Q. 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ä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.  Google Scholar

[3]

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

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

[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.  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. Zhang, Q. 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 Options

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

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

Download full-size image

Download as PowerPoint slide

Figure 4.  shuttle graph
Figure Options

Download full-size image

Download as PowerPoint slide

[1]

Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907
[2]

Jong Yoon Hyun, Yoonjin Lee, Yansheng Wu. Connection of $ p $-ary $ t $-weight linear codes to Ramanujan Cayley graphs with $ t+1 $ eigenvalues. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2020133
[3]

Raz Kupferman, Cy Maor. The emergence of torsion in the continuum limit of distributed edge-dislocations. Journal of Geometric Mechanics, 2015, 7 (3) : 361-387. doi: 10.3934/jgm.2015.7.361

2019 Impact Factor: 1.233

Tools

Metrics

  • PDF downloads (80)
  • HTML views (432)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences