Generalized stepwise transmission irregular graphs

Alizadeh, Yaser (author), Klavžar, Sandi (author), Molaee, Zohre (author)

The transmission ${\rm Tr}_G(u)$ of a vertex $u$ of a connected graph $G$ is the sum of distances from $u$ to all other vertices. $G$ is a stepwise transmission irregular (STI) graph if $|{\rm Tr}_G(u) - {\rm Tr}_G(v)|= 1$ holds for any edge $uv\in E(G)$. In this paper, generalized STI graphs are introduced as the graphs $G$ such that for some $k\ge 1$ we have $|{\rm Tr}_G(u) - {\rm Tr}_G(v)|= k$ for any edge $uv$ of $G$. It is proved that generalized STI graphs are bipartite and that as soon as the minimum degree is at least $2$, they are $2$-edge connected. Among the trees, the only generalized STI graphs are stars. The diameter of STI graphs is bounded and extremal cases discussed. The Cartesian product operation is used to obtain highly connected generalized STI graphs. Several families of generalized STI graphs are constructed.

• Language: English
• Keywords: graph distance, transmission of vertex, stepwise transmission irregular graph, Cartesian product of graphs
• Work type: Article
• Typology: 1.01 - Original Scientific Article
• Organization: FMF - Faculty of Mathematics and Physics
• Publication status: Published
• Publication version: Version of Record
• Publication date: 01.01.2024
• Year: 2024
• Number of pages: Str. 5875-5883
• Numbering: Vol. 38, no. 16
• PID: 20.500.12556/RUL-176924
• UDC: 519.17
• ISSN on article: 0354-5180
• DOI: 10.2298/FIL2416875A
• COBISS.SI-ID: 212465411
• Publication date in RUL: 15.12.2025

Record is a part of a journal

• Title: Filomat
• Shortened title: Filomat
• Publisher: Department of Mathematics and Informatics, Faculty of Science and Mathematics, University of Niš
• ISSN: 0354-5180
• COBISS.SI-ID: 1024191828

Secondary language

• Language: Slovenian
• Keywords: razdalja v grafu, celotna razdalja vozlišča, stopenjsko iregularen graf, kartezični produkt grafov