1-Edge contraction: Total vertex stress and confluence number

Document Type : Original paper

Authors

1 Mathematic Research Center, Mary Matha Arts and Science College, Mananthavady, Kerala, India

2 Independant Mathematics Researcher, City of Tshwane, South Africa & Visiting Faculty at CHRIST (Deemed to be a University), Bangalore, India

Abstract

This paper introduces certain relations between $1$-edge contraction and the total vertex stress and the confluence number of a graph. A main result states that if a graph $G$ with $\zeta(G)=k\geq 2$ has an edge $v_iv_j$ and a $\zeta$-set $\mathcal{C}_G$ such that $v_i,v_j\in \mathcal{C}_G$ then, $\zeta(G/v_iv_j) = k-1$. In general, either $\mathcal{S}(G/e_i) \leq \mathcal{S}(G/e_j)$ or $\mathcal{S}(G/e_j) \leq \mathcal{S}(G/e_i)$ is true. This observation leads to an investigation into the question: for which edge(s) $e_i$ will $\mathcal{S}(G/e_i) = \max\{\mathcal{S}(G/e_j):e_j \in E(G)\}$ and for which edge(s) will $\mathcal{S}(G/e_j) = \min\{\mathcal{S}(G/e_\ell):e_\ell \in E(G)\}$?

Keywords

Main Subjects

References

[1] J.A. Bondy and U.S.R Murty, Graph Theory with Applications, Macmillan Press London, 1976.
[2] M. Changat, P.G. Narasimha-Shenoi, and G. Seethakuttyamma, Betweenness in graphs: a short survey on shortest and induced path betweenness, AKCE Int. J. Graphs Comb. 16 (2019), no. 1, 96–109.
https://doi.org/10.1016/j.akcej.2018.06.007
[3] A.A. Dobrynin, Wiener index of subdivisions of a tree, Siberian Electron. Math. Reports 16 (2019), 1581–1586.
https://doi.org/10.33048/semi.2019.16.109
[4] A.A. Dobrynin, On the Wiener index of the forest induced by contraction of edges in a tree, MATCH Commun. Math. Comp. Chem. 16 (2021), no. 2, 321–326.
[5] F. Harary, Graph Theory, Addison-Wesley, 1969.
[6] J. Kok and J. Shiny, On parametric equivalence, isomorphism and uniqueness: Cycle related graphs, Open J. Discrete Appl. Math. 4 (2021), no. 1, 45–51.
https://doi.org/10.30538/psrp-odam2021.0053
[7] J. Kok and J. Shiny, On parametric equivalent, isomorphic and unique sets, Open J. Discrete Appl. Math. 4 (2021), no. 1, 19–24.
https://doi.org/10.30538/psrp-odam2021.0050
[8] J. Kok, J. Shiny, and V. Ajitha, Total vertex stress alteration in cycle related graphs, Matematichki Bilten 44 (2020), no. 2, 149–162.
[9] A. Shimbel, Structural parameters of communication networks, The Bulletin of Mathematical Biophysics 1 (1953), no. 4, 501–507.
https://doi.org/10.1007/BF02476438
[10] J. Shiny and V. Ajitha, Stress regular graphs, Malaya J. Mat. 8 (2020), no. 3, 1152–1154.
[11] D.B. West, Introduction to Graph Theory, Prentice-Hall Upper Saddle River, 1996.
Communications in Combinatorics and Optimization
Volume 9, Issue 3
September 2024
Pages 527-538

Files

Share

How to cite

Statistics