Concatenating bipartite graphs

Abstract: Let

x, y i n (0, 1]

and let

A, B, C

be disjoint nonempty subsets of a graph

G

, where every vertex in

A

has at least

x | B |

neighbours in

B

, and every vertex in

B

has at least

y | C |

neighbours in

C

. We denote by

p h i (x, y)

the maximum

z

such that, in all such graphs

G

, there is a vertex

v

in

C

that is joined to at least

z | A |

vertices in

A

by two-edge paths. The function

p h i

is interesting, and we investigate some of its properties. For instance, we show that it is symmetric in

x

and

y

, and that it has a discontinuity at

x = y = 1 / k

for all integers

k > 1

. We raise a number of questions and conjectures.

Full work available at URL: https://arxiv.org/abs/1902.10878

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

Cites Work

This page was built for publication: Concatenating bipartite graphs