Jump-number of means on graphs (Q1582483)

From MaRDI portal
Revision as of 21:36, 10 December 2024 by Import241208061232 (talk | contribs) (Normalize DOI.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Jump-number of means on graphs
scientific article

    Statements

    Jump-number of means on graphs (English)
    0 references
    0 references
    0 references
    0 references
    14 January 2001
    0 references
    A mapping \(f: V^n\to V\) is called idempotent if it maps every constant tuple to that constant and it is called \(n\)-mean if it is also symmetric. Let the girth of a graph be the length of a shortest cycle, and let the jump-number \(J_f\) of a mapping \(f: V(G_1)\to V(G_2)\) be the least \(\lambda\in \mathbb{N}_0\cup\{\infty\}\) such that the shortest path distance \(d_{G_2}(f(x),f(y))\leq \lambda\leq d_{G_1}(x,y)\) for all \(x,y\in V(G_1)\). Let the Hamming \(n\)th power of a graph \(G\) be the graph with vertex set \(V(G)^n\) such that \((x_1,\dots, x_n)\) is adjacent to \((y_1,\dots, y_n)\) iff there is at most one \(k\in \{1,\dots, n\}\) with \(x_k\neq y_k\) and \(x_ky_k\in E(G)\). The authors prove that, for every \(n> 1\) and \(g\geq 3\), we have: For every graph \(G\) with girth \(g\) and every \(n\)-mean \(f: V(G)^n\to V(G)\) the jump-number of \(f\) is at least \(\lceil\min\{{g\over 4},{g-1\over 4}\}\rceil\) if \(V(G)^n\) is equipped with the Hamming power of \(G\).
    0 references
    means
    0 references
    jump-number
    0 references
    0 references

    Identifiers