BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
We prove that deciding whether the edge set of a graph can be partitionned into two spanning trees with orientation constraints is NP-complete. If P = NP then this disproves a conjecture of Recski.
We provide the directed counterpart of a slight extension of Katoh and Tanigawa's result on rooted-tree decompositions with matroid constraints. Our result characterises digraphs having a packing of arborescences with matroid constraints. It is a proper extension of Edmonds' result on packing of spanning arborescences and implies - using a general orientation result of Frank - the above result of Katoh and Tanigawa. We also give a complete description of the convex hull of the incidence vectors of the basic packings of arborescences and prove that the mimimum cost version of the problem can be solved in polynomial time.
A graph G is called (2k, k)-connected if G is 2k-edge-connected and G-v is k-edge-connected for every vertex v. The study of (2k, k)-connected graphs is motivated by a conjecture of Frank which states that a graph has a 2-vertex-connected orientation if and only if it is (4, 2)-connected. In this paper, we provide a construction of the family of (2k, k)-connected graphs for k even which generalizes the construction given by Jordán for k = 2. We also solve the corresponding connectivity augmentation problem: given a graph G and an integer k \geq 2, what is the minimum number of edges to be added to make G (2k, k)-connected. Both these results are based on a new splitting-off theorem for (2k, k)-connected graphs.
We disprove a conjecture of Frank stating that each weakly 2k-connected has a k-vertex-connected orientation. For k at least 3, we also prove that the problem of deciding whether a graph has a k-vertex-connected orientation is NP-complete.
We prove that every (6k + 2l, 2k)-connected simple graph contains k rigid and l connected edge-disjoint spanning subgraphs. This implies a theorem of Jackson and Jordán [4] and a theorem of Jordán [6] on packing of rigid spanning subgraphs. Both these results are generalizations of the classical result of Lovász and Yemini [9] saying that every 6-connected graph is rigid for which our approach provides a transparent proof. Our result also gives two improved upper bounds on the connectivity of graphs that have interesting properties: (1) every 8-connected graph packs a spanning tree and a 2-connected spanning subgraph; (2) every 14-connected graph has a 2-connected orientation.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.