Transmission of a graph vertex is the sum of its distances to all other vertices of the graph. A graph is transmission irregular (TI) if no two of its vertices have equal transmissions. Stošić and Damnjanović (Comput Appl Math 45:80 2026) showed that for any vertex v of a TI tree T the components of <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$T-v$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>T</mi> <mo>-</mo> <mi>v</mi> </mrow> </math></EquationSource> </InlineEquation> have pairwise distinct orders, so that if a TI tree has maximum vertex degree <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\Delta $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Δ</mi> </math></EquationSource> </InlineEquation> then its order is at least <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\frac{\Delta (\Delta +1)}{2}+1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfrac> <mrow> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi mathvariant="normal">Δ</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mn>2</mn> </mfrac> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation>. Here we answer the open problem of Stošić and Damnjanović by showing that a TI tree of maximum vertex degree <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\Delta $</EquationSource> <EquationSource Format="MATHML"><math> <mi mathvariant="normal">Δ</mi> </math></EquationSource> </InlineEquation> and order exactly <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$\frac{\Delta (\Delta +1)}{2}+1$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mfrac> <mrow> <mi mathvariant="normal">Δ</mi> <mo stretchy="false">(</mo> <mi mathvariant="normal">Δ</mi> <mo>+</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mrow> <mn>2</mn> </mfrac> <mo>+</mo> <mn>1</mn> </mrow> </math></EquationSource> </InlineEquation> exists for each <InlineEquation ID="IEq6"> <EquationSource Format="TEX">$\Delta \ge 3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="normal">Δ</mi> <mo>≥</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>.

A family of transmission irregular trees answering a problem of Stošić and Damnjanović

期刊论文
发表日期：

2026年3月31日

查看全文

Dragan Stevanović

摘要

Transmission of a graph vertex is the sum of its distances to all other vertices of the graph. A graph is transmission irregular (TI) if no two of its vertices have equal transmissions. Stošić and Damnjanović (Comput Appl Math 45:80 2026) showed that for any vertex v of a TI tree T the components of $T-v$ $T - v$ have pairwise distinct orders, so that if a TI tree has maximum vertex degree $\Delta $ $Δ$ then its order is at least $\frac{\Delta (\Delta +1)}{2}+1$ $\frac{Δ (Δ + 1)}{2} + 1$ . Here we answer the open problem of Stošić and Damnjanović by showing that a TI tree of maximum vertex degree $\Delta $ $Δ$ and order exactly $\frac{\Delta (\Delta +1)}{2}+1$ $\frac{Δ (Δ + 1)}{2} + 1$ exists for each $\Delta \ge 3$ $Δ \geq 3$ .