We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
WEIGHTED EULERIAN EXTENSIONS OF RANDOM GRAPHS.
- Authors
GANESAN, GHURUMURUHAN
- 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.
- Subjects
EULERIAN graphs; WEIGHTED graphs; RANDOM graphs; EULER'S numbers; ODD numbers
- Publication
Gulf Journal of Mathematics, 2024, Vol 16, Issue 2, p1
- ISSN
2309-4966
- Publication type
Article
- DOI
10.56947/gjom.v16i2.1866