7 papers
Neighborhood Complexity and Radius-1 Merge-Width in Monadically Dependent Graph Classes
Jan Dreier, Nikolas Mählmann, Rose McCarty +2
Monadic dependence is a proposed structural dividing line for fixed-parameter tractability of first-order model checking on hereditary graph classes. A graph class is \emph{monadic…
A combinatorial framework for clustering graph states: Algorithms and hardness for rank-integrity
Romain Bourneuf, Nathan Claudet, Sang Yoon Kim +3
We introduce a new notion of distance between two graph states and on the same set of qubits. This distance is the minimum number of ancilla qubits in a gr…
Biclique decompositions from Welzl orders
Jean Cardinal, Rose McCarty, Yelena Yuditsky
A biclique decomposition of a graph is a partition of its edges into complete bipartite subgraphs. We consider graphs whose vertices can be ordered such that the neighborhood of ev…
The Structure of Circle Graph States
Frederik Hahn, Rose McCarty, Hendrik Poulsen Nautrup +1
Circle graph states are a structurally important family of graph states. The family's entanglement is a priori high enough to allow for universal measurement-based quantum computat…
The structure of group-labeled graphs forbidding an immersion
Rose McCarty, Caleb McFarland, Paul Wollan
A -labeled graph is an oriented graph with edges invertibly labeled by a group . We prove a structure theorem for -labeled graphs which forbid a fixed -labeled grap…
Graphs whose Eulerian trails have unique labels
Donggyu Kim, Rose McCarty, Caleb McFarland
Consider an undirected graph whose edges are labeled invertibly in a group. When does every Eulerian trail from one fixed vertex to another have the same label? We give a precise s…