Some Methods for Constructing Infinite Families of Quasi-Strongly Regular Graphs

Title:Some Methods for Constructing Infinite Families of Quasi-Strongly Regular Graphs

Volume: 14 Issue: 8

Author(s): Gholam Hassan Shirdel*Adel Asgari

Affiliation:

• Department of Mathematics, Faculty of Sciences, University of Qom, Qom,Iran

Keywords: Regular graph, Strongly regular graph, Semi-strongly regular graph, Composition, Combining graphs, Common neighbors.

Abstract: Objective: In this article, we examined some method of constructing infinite families of semi-strongly regular graphs, Also we obtained a necessary condition for the composition of several graphs to be semi-strongly regular graphs, and using it, we have constructed some infinite families of semi-strongly regular graphs, Also by using the Cartesian product of two graphs, we have constructed some infinite families of semi-strongly regular graphs.

Intoduction: A regular graph is called strongly regular graph if the number of common neighbors of two adjacent vertices is a non-negative integer λ and the number of common neighbors of two nonadjacent vertices is a non- negative integer μ. Strongly regular graph introduced in 1963. Subsequently, studying of this graphs and methods of constructing them was a very important part of graph theory, There are two important branches in studying strongly regular graphs.

Mehtods: A pairwise balanced incomplete bloc design (PBIBD) is a collection of subsets β of a vset X called blocks such that every pair of elements of X appears in exactly blocks,. If each block has k elements this design is called a 2-(v,k,λ) design, or simply a 2-design or a block design. We denote the number of blocks in β by b and it is easy to see that for each element x of X the number of blocks containing x is a constant (denoted by r)

Result: We use a method of constructing new graph from the old ones, introduced and named as composition of graphs. A block design is usually displayed with an array, so that each column represents a block.

Discussion: Interesting graphs have been introduced with certain properties that have proximity kinship with strongly regular graphs and quasi-strongly regular graphs.

Conclusion: Strongly regular graphs are an important and interesting family of graphs that are generalized in a variety of ways. For example, the strongly regular digraphs, (λ, μ)- graphs and quasistrongly regular graphs are some generalizations of these graphs. In present article, in addition to a review of several methods of constructing strongly regular graphs.

Cite this article as:

Shirdel Hassan Gholam *, Asgari Adel , Some Methods for Constructing Infinite Families of Quasi-Strongly Regular Graphs, Recent Advances in Computer Science and Communications 2021; 14 (8) . https://dx.doi.org/10.2174/2666255813999200628093740

DOI https://dx.doi.org/10.2174/2666255813999200628093740	Print ISSN 2666-2558
Publisher Name Bentham Science Publisher	Online ISSN 2666-2566