Digraphs in which every $t$ vertices share exactly $λ$ out-neighbors and exactly $λ$ in-neighbors
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917672724201472 |
|---|---|
| author | Chu, Hojin Kim, Suh-Ryung |
| author_facet | Chu, Hojin Kim, Suh-Ryung |
| contents | In this paper, we introduce the notion of two-way $(t,λ)$-liking digraphs as a way to extend the results for generalized friendship graphs.
A two-way $(t,λ)$-liking digraph is a digraph in which every $t$ vertices have exactly $λ$ common out-neighbors and $λ$ common in-neighbors.
We first show that if $λ\ge 2$, then a two-way $(2,λ)$-liking digraph of order $n$ is $k$-diregular for a positive integer $k$ satisfying the equation $(n-1)λ=k(k-1)$.
This result is comparable to the result by Bose and Shrikhande in 1969 and actually extends it.
Another main result is that if $t \ge 3$, then the complete digraph on $t+λ$ vertices is the only two-way $(t,λ)$-liking digraph.
This result can stand up to the result by Carstens and Kruse in 1977 and essentially extends it.
In addition, we find that two-way $(t, λ)$-liking digraphs are closely linked to symmetric block designs and extend some existing results of $(t, λ)$-liking digraphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_13293 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Digraphs in which every $t$ vertices share exactly $λ$ out-neighbors and exactly $λ$ in-neighbors Chu, Hojin Kim, Suh-Ryung Combinatorics 05C20, 05C75 In this paper, we introduce the notion of two-way $(t,λ)$-liking digraphs as a way to extend the results for generalized friendship graphs. A two-way $(t,λ)$-liking digraph is a digraph in which every $t$ vertices have exactly $λ$ common out-neighbors and $λ$ common in-neighbors. We first show that if $λ\ge 2$, then a two-way $(2,λ)$-liking digraph of order $n$ is $k$-diregular for a positive integer $k$ satisfying the equation $(n-1)λ=k(k-1)$. This result is comparable to the result by Bose and Shrikhande in 1969 and actually extends it. Another main result is that if $t \ge 3$, then the complete digraph on $t+λ$ vertices is the only two-way $(t,λ)$-liking digraph. This result can stand up to the result by Carstens and Kruse in 1977 and essentially extends it. In addition, we find that two-way $(t, λ)$-liking digraphs are closely linked to symmetric block designs and extend some existing results of $(t, λ)$-liking digraphs. |
| title | Digraphs in which every $t$ vertices share exactly $λ$ out-neighbors and exactly $λ$ in-neighbors |
| topic | Combinatorics 05C20, 05C75 |
| url | https://arxiv.org/abs/2405.13293 |