Weighted Eulerian extensions of random graphs

Main Article Content

Ghurumuruhan Ganesan

Abstract

The Eulerian extension number of any graph H (i.e. the minimum number of edges needed to be added to make H Eulerian) is at least t(H), half the number of odd degree vertices of H. In this paper we consider weighted Eulerian extensions of a random graph G where we add edges of bounded weights and use an iterative probabilistic method to obtain sufficient conditions for the weighted Eulerian extension number of G to grow linearly with t(G). We derive our conditions in terms of the average edge probabilities and edge density and also show that bounded extensions are rare by estimating the skewness of a fixed weighted extension. Finally, we briefly describe a decomposition involving Eulerian extensions of G to convert a large dataset into small dissimilar batches.

Downloads

Download data is not yet available.

Article Details

How to Cite
Ganesan, G. (2024). Weighted Eulerian extensions of random graphs. Gulf Journal of Mathematics, 16(2), 1-11. https://doi.org/10.56947/gjom.v16i2.1866
Section
Articles