Faculty Publications

Search Results

Now showing 1 - 6 of 6

Separation Dimension of Graphs and Hypergraphs
(Springer New York LLC barbara.b.bertram@gsk.com, 2016) Basavaraju, M.; Sunil Chandran, L.S.; Golumbic, M.C.; Mathew, R.; Rajendraprasad, D.
Separation dimension of a hypergraph H, denoted by ?( H) , is the smallest natural number k so that the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph H is equal to the boxicity of the line graph of H. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension. In this paper, we study the separation dimension of hypergraphs and graphs. © 2015, Springer Science+Business Media New York.
Maximal Induced Matchings in Triangle-Free Graphs
(Wiley-Liss Inc. info@wiley.com, 2016) Basavaraju, M.; Heggernes, P.; van 't'Hof, P.; Saei, R.; Villanger, Y.
An induced matching in a graph is a set of edges whose endpoints induce a 1-regular subgraph. It is known that every n-vertex graph has at most (Formula presented.) maximal induced matchings, and this bound is the best possible. We prove that every n-vertex triangle-free graph has at most (Formula presented.) maximal induced matchings; this bound is attained by every disjoint union of copies of the complete bipartite graph K3, 3. Our result implies that all maximal induced matchings in an n-vertex triangle-free graph can be listed in time (Formula presented.), yielding the fastest known algorithm for finding a maximum induced matching in a triangle-free graph. © 2015 Wiley Periodicals, Inc.
Separation dimension and sparsity
(Wiley-Liss Inc. info@wiley.com, 2018) Alon, N.; Basavaraju, M.; Sunil Chandran, L.S.; Mathew, R.; Rajendraprasad, D.
The separation dimension ???(G) of a hypergraph G is the smallest natural number k for which the vertices of G can be embedded in Rk so that any pair of disjoint edges in G can be separated by a hyperplane normal to one of the axes. Equivalently, it is the cardinality of a smallest family F of total orders of V(G), such that for any two disjoint edges of G, there exists at least one total order in F in which all the vertices in one edge precede those in the other. Separation dimension is a monotone parameter; adding more edges cannot reduce the separation dimension of a hypergraph. In this article, we discuss the influence of separation dimension and edge-density of a graph on one another. On one hand, we show that the maximum separation dimension of a k-degenerate graph on n vertices is O(k lg lg n) and that there exists a family of 2-degenerate graphs with separation dimension ?(lg lg n). On the other hand, we show that graphs with bounded separation dimension cannot be very dense. Quantitatively, we prove that n-vertex graphs with separation dimension s have at most 3(4 lg n)s?2 edges. We do not believe that this bound is optimal and give a question and a remark on the optimal bound. © 2018 Wiley Periodicals, Inc.
On induced colourful paths in triangle-free graphs
(Elsevier B.V., 2019) Babu, J.; Basavaraju, M.; Sunil Chandran, L.S.; Francis, M.C.
Given a graph G=(V,E) whose vertices have been properly coloured, we say that a path in G is colourful if no two vertices in the path have the same colour. It is a corollary of the Gallai–Roy–Vitaver Theorem that every properly coloured graph contains a colourful path on ?(G) vertices. We explore a conjecture that states that every properly coloured triangle-free graph G contains an induced colourful path on ?(G) vertices and prove its correctness when the girth of G is at least ?(G). Recent work on this conjecture by Gyárfás and Sárközy, and Scott and Seymour has shown the existence of a function f such that if ?(G)?f(k), then an induced colourful path on k vertices is guaranteed to exist in any properly coloured triangle-free graph G. © 2018 Elsevier B.V.
Gallai’s Path Decomposition for 2-degenerate Graphs
(Discrete Mathematics and Theoretical Computer Science, 2023) Anto, N.; Basavaraju, M.
Gallai’s path decomposition conjecture states that if G is a connected graph on n vertices, then the edges of G can be decomposed into at most ⌈ n2 ⌉ paths. A graph is said to be an odd semi-clique if it can be obtained from a clique on 2k + 1 vertices by deleting at most k − 1 edges. Bonamy and Perrett asked if the edges of every connected graph G on n vertices can be decomposed into at most ⌊ n2 ⌋ paths unless G is an odd semi-clique. A graph G is said to be 2-degenerate if every subgraph of G has a vertex of degree at most 2. In this paper, we prove that the edges of any connected 2-degenerate graph G on n vertices can be decomposed into at most ⌊ n2 ⌋ paths unless G is a triangle. © 2023 by the author(s)
Maximal induced matchings in K4-free and K5-free graphs
(Elsevier B.V., 2024) Basavaraju, M.; van Leeuwen, E.J.; Saei, R.
An induced matching in a graph is a set of edges whose endpoints induce a 1-regular subgraph. It is known that every graph on n vertices has at most 10n/5?1.5849n maximal induced matchings, and this bound is the best possible as any disjoint union of complete graphs K5 forms an extremal graph. It is also known that the bound drops to 3n/3?1.4423n when the graphs are restricted to the class of triangle-free (K3-free) graphs. The extremal graphs, in this case, are known to be the disjoint unions of copies of K3,3. Along the same line, we study the maximum number of maximal induced matchings when the graphs are restricted to K5-free graphs and K4-free graphs. We show that every K5-free graph on n vertices has at most 6n/4?1.5651n maximal induced matchings and the bound is the best possible obtained by any disjoint union of copies of K4. When the graphs are restricted to K4-free graphs, the upper bound drops to 8n/5?1.5158n, and it is achieved by the disjoint union of copies of the wheel graph W5. © 2024 The Author(s)

Faculty Publications

Browse

Filters

Settings

Sort By

Results per page

Search Results