5 papers
Completely Independent Steiner Trees
Anil Maheshwari, Karthik Murali, Michiel Smid
Spanning trees are fundamental for efficient communication in networks. For fault-tolerant communication, it is desirable to have multiple spanning trees to ensure resilience again…
Computing Vertex and Edge Connectivity of Graphs Embedded with Crossings
Therese Biedl, Prosenjit Bose, Karthik Murali
Vertex connectivity and edge connectivity are fundamental concepts in graph theory that have been widely studied from both structural and algorithmic perspectives. The focus of thi…
Cops and Robbers for Graphs on Surfaces with Crossings
Prosenjit Bose, Pat Morin, Karthik Murali
Cops and Robbers is a game played on a graph where a set of cops attempt to capture a single robber. The game proceeds in rounds, where each round first consists of the cops' turn,…
On 1-Planar Graphs with Bounded Cop-Number
Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari +1
Cops and Robbers is a type of pursuit-evasion game played on a graph where a set of cops try to capture a single robber. The cops first choose their initial vertex positions, and l…
Variants of the Gyà rfà s-Sumner Conjecture: Oriented Trees and Rainbow Paths
Manu Basavaraju, L. Sunil Chandran, Mathew C. Francis +1
Given a finite family of graphs, we say that a graph is "-free" if does not contain any graph in as a subgraph. A vertex-colored gr…