On the Extendability of Quasi-Strongly Regular Graphs with Diameter 2

被引:0
作者
Hermina Alajbegović
Almir Huskanović
Štefko Miklavič
Primož Šparl
机构
[1] University of Zenica,Faculty of Mechanical Engineering
[2] University of Primorska,Andrej Marušič Institute
[3] University of Ljubljana,Faculty of Education
[4] Institute of Mathematics,undefined
[5] Physics and Mechanics,undefined
来源
Graphs and Combinatorics | 2018年 / 34卷
关键词
Regular graph; Quasi-strongly regular graph; Diameter 2; -extendable;
D O I
暂无
中图分类号
学科分类号
摘要
Let ℓ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell $$\end{document} denote a non-negative integer and let Γ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Gamma $$\end{document} be a connected graph of even order at least 2ℓ+2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2 \ell +2$$\end{document}. It is said that Γ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Gamma $$\end{document} is ℓ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell $$\end{document}-extendable if it contains a matching of size ℓ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\ell $$\end{document} and if every such matching is contained in a perfect matching of Γ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Gamma $$\end{document}. A connected regular graph Γ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Gamma $$\end{document} is quasi-strongly regular with parameters (n,k,λ;μ1,μ2,…,μs)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(n, k, \lambda ; \mu _1, \mu _2, \ldots , \mu _s)$$\end{document}, if it is a k-regular graph on n vertices, such that any two adjacent vertices have exactly λ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\lambda $$\end{document} common neighbours and any two distinct and non-adjacent vertices have exactly μi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mu _i$$\end{document} common neighbours for some 1≤i≤s\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \le i \le s$$\end{document}. The grade of Γ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Gamma $$\end{document} is the number of indices 1≤i≤s\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1 \le i \le s$$\end{document} for which there exist two distinct and non-adjacent vertices in Γ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Gamma $$\end{document} with μi\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mu _i$$\end{document} common neighbours. In this paper we study the extendability of quasi-strongly regular graphs of diameter 2 and grade 2. In particular, we classify the 2-extendable members of this class of graphs.
引用
收藏
页码:711 / 726
页数:15
相关论文
共 35 条
[1]  
Chan O(1995)On Discrete Math. 146 19-32
[2]  
Chen CC(1992)-extendable abelian Cayley graphs Australas. J. Comb. 6 209-219
[3]  
Yu Q(2014)On the classification of 2-extendable Cayley graphs on dihedral groups Electron. J. Comb. 21 P2.34-244
[4]  
Chen CC(2017)The extendability of matchings in strongly regular graphs Eur. J. Comb. 62 232-90
[5]  
Liu J(1980)Max-cut and extendability of matchings in distance-regular graphs Networks 10 87-451
[6]  
Yu Q(2006)Maximum degree in graphs of diameter 2 Linear Multilinear Algebra 54 437-208
[7]  
Cioabă SM(2004)On quasi-strongly regular graphs Electron. J. Comb. 11 R7-82
[8]  
Li W(1992)On regular factors in regular graphs with small radius Australas. J. Comb. 6 187-140
[9]  
Cioabă SM(2002)Matching extensions of strongly regular graphs J. Graph Theory 40 75-101
[10]  
Koolen J(1996)Hamiltonian cycles in Discrete Math. 148 133-1423