On the extension of connected irregular (λ,μ)-graphs

摘要

Let λ and μ be any nonnegative integers. A graph G is called a (λ,μ)-graph if every pair of adjacent vertices have λ common neighbors, and every pair of non-adjacent vertices have μ common neighbors. Thus, (λ,μ)-graphs are generalization of strongly regular graphs obtained by lessening the regularity property on vertex degrees. In this paper, we will show that a (λ, 1)-graph, with n vertices, is of type K_1 ∨(s_2K_2 ∪s_3K_3 ∪…∪s_tK_t ) such that s_t≥0, for all i = 1, ..., t and 1 + 2s_2 + ... + ts_t = n. Note that λ can take several values in the same graph.