\(\rho\)-valuations for some stunted trees (Q2433736): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
ReferenceBot (talk | contribs) Changed an Item |
||
(2 intermediate revisions by 2 users not shown) | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / full work available at URL | |||
Property / full work available at URL: https://doi.org/10.1016/j.disc.2006.05.026 / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2010363941 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Combinatorial Nullstellensatz / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3663322 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q4401957 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5589124 / rank | |||
Normal rank |
Latest revision as of 22:26, 24 June 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | \(\rho\)-valuations for some stunted trees |
scientific article |
Statements
\(\rho\)-valuations for some stunted trees (English)
0 references
30 October 2006
0 references
A \(\rho\)-valuation of a graph \(G\) with \(n\) edges is an injection of the vertex set into the set \(\{0,\dots,2n\}\) so that, if the edge labels induced by the absolute value of the difference of the vertex labels are \(a_1,a_2,\dots,a_n\), then \(a_i=i\) or \(a_i=2n+1-i\). This is one of the valuations introduced by \textit{A. Rosa} [Theory Graphs, Int. Symp. Rome 1966, 349--355 (1967; Zbl 0193.53204)]. There is a conjecture due to \textit{A. Kotzig} [Util. Math. 4, 261--290 (1973; Zbl 0277.05102)] that all trees have \(\rho\)-valuations. The article under review gives a partial answer to this conjecture. A tree with \(n\) edges is stunted if its edges can be linearly ordered \(e_1,e_2,\dots,e_n\) so that \(e_1\) and \(e_2\) share a vertex, and for all \(j=3,\dots,n\), \(e_j\) shares a vertex with at least one edge \(e_k\) satisfying \(2k\leq j-1\). Using the combinatorial Nullstellensatz by \textit{N. Alon} [Comb. Probab. Comput. 8, 7--29 (1999; Zbl 0920.05026)], the author proves that if \(p=2n+1\) is prime, then every stunted tree with \(n\) edges has a \(\rho\)-valuation. As a corollary, every stunted tree with \(n\) edges cyclically decomposes the complete graph \(K_{2n+1}\) by a result of A. Rosa. A tree \(T\) with \(n\) edges cyclically decomposes \(K_{2n+1}\) if there exists an injection \(\psi:V(T) \to \mathbb{Z}_{2n+1}\) such that for all distinct \(i,j\in \mathbb{Z}_{2n+1}\), there exists a unique \(k\in \mathbb{Z}_{2n+1}\) with the property that there is a pair of adjacent vertices \(u\), \(v\) of \(T\) satisfying \(\{i,j\}\equiv \{\psi(u)+k\), \(\psi(v)+k\}\).
0 references
combinatorial Nullstellensatz
0 references