4
$\begingroup$

Is there a name for graphs of the following type?

enter image description here

Namely, it has an integer function $\ell$ on the set of the vertex set such that $v$ is adjacent to $w$ if and only if $$|\ell(v)-\ell(w)|\le 1.$$

Postscript. Maybe I can call it multipath? It is a path with multiplied vertices as described in this answer.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Equivalently: start from a disjoint union of path graphs and replace any of the vertices by cliques. $\endgroup$
    – Sam Hopkins
    Commented Dec 6, 2022 at 20:21
  • 3
    $\begingroup$ Related MO question: Does the notion of graphs with vertex multiplicity exist? $\endgroup$
    – Timothy Chow
    Commented Dec 7, 2022 at 1:57
  • 1
    $\begingroup$ "lexicographic product" $\endgroup$
    – Martin Rubey
    Commented Dec 7, 2022 at 11:02
  • 2
    $\begingroup$ Regarding the suggestion of "multipath," if I heard that term without any definition and had to guess what it meant, I would guess that it would be a path with possibly repeated edges rather than a path whose vertices had multiplicity. $\endgroup$
    – Timothy Chow
    Commented Dec 7, 2022 at 15:01
  • 2
    $\begingroup$ @TimothyChow: it is, more precisely (and trivially), the so called lexicographic product or local join $P_n[K_{i_1}, \dots, K_{i_n}]$. See eg. Sabidussi, "Graph derivatives" or item 16 of Section 2.7 in Cvetkovic, Doob, Sachs, "Spectra of Graphs". In particular, 2.7.16 of the latter exhibits the eigenvalues of $G[H_1,\dots,H_n]$, provided that the $H_i$ are regular. In the case at hand, we should get $-1$ with multiplicity $\sum n_i - n$ together with the eigenvalues of the matrix $(a_{i, j} n_j + \delta_{i, j} (n_j - 1))$, where $(a_{i,j})$ is the adjacency matrix of the path. $\endgroup$
    – Martin Rubey
    Commented Dec 7, 2022 at 16:02

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .