Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userArc-disjoint in- and out-branchings rooted at the same vertex in compositions of digraphs
95
0
0.0
(
0
)
Added by
Gregory Gutin
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
A digraph $D=(V, A)$ has a good pair at a vertex $r$ if $D$ has a pair of arc-disjoint in- and out-branchings rooted at $r$. Let $T$ be a digraph with $t$ vertices $u_1,dots , u_t$ and let $H_1,dots H_t$ be digraphs such that $H_i$ has vertices $u_{i,j_i}, 1le j_ile n_i.$ Then the composition $Q=T[H_1,dots , H_t]$ is a digraph with vertex set ${u_{i,j_i}mid 1le ile t, 1le j_ile n_i}$ and arc set $$A(Q)=cup^t_{i=1}A(H_i)cup {u_{ij_i}u_{pq_p}mid u_iu_pin A(T), 1le j_ile n_i, 1le q_ple n_p}.$$ When $T$ is arbitrary, we obtain the following result: every strong digraph composition $Q$ in which $n_ige 2$ for every $1leq ileq t$, has a good pair at every vertex of $Q.$ The condition of $n_ige 2$ in this result cannot be relaxed. When $T$ is semicomplete, we characterize semicomplete compositions with a good pair, which generalizes the corresponding characterization by Bang-Jensen and Huang (J. Graph Theory, 1995) for quasi-transitive digraphs. As a result, we can decide in polynomial time whether a given semicomplete composition has a good pair rooted at a given vertex.
rate research
Read More
We prove that every digraph of independence number at most 2 and arc-connectivity at least 2 has an out-branching $B^+$ and an in-branching $B^-$ which are arc-disjoint (we call such branchings good pair). This is best possible in terms of the arc-connectivity as there are infinitely many strong digraphs with independence number 2 and arbitrarily high minimum in-and out-degrees that have good no pair. The result settles a conjecture by Thomassen for digraphs of independence number 2. We prove that every digraph on at most 6 vertices and arc-connectivity at least 2 has a good pair and give an example of a 2-arc-strong digraph $D$ on 10 vertices with independence number 4 that has no good pair. We also show that there are infinitely many digraphs with independence number 7 and arc-connectivity 2 that have no good pair. Finally we pose a number of open problems.
Given a digraph $G$, a set $Xsubseteq V(G)$ is said to be absorbing set (resp. dominating set) if every vertex in the graph is either in $X$ or is an in-neighbour (resp. out-neighbour) of a vertex in $X$. A set $Ssubseteq V(G)$ is said to be an independent set if no two vertices in $S$ are adjacent in $G$. A kernel (resp. solution) of $G$ is an independent and absorbing (resp. dominating) set in $G$. We explore the algorithmic complexity of these problems in the well known class of interval digraphs. A digraph $G$ is an interval digraph if a pair of intervals $(S_u,T_u)$ can be assigned to each vertex $u$ of $G$ such that $(u,v)in E(G)$ if and only if $S_ucap T_v eqemptyset$. Many different subclasses of interval digraphs have been defined and studied in the literature by restricting the kinds of pairs of intervals that can be assigned to the vertices. We observe that several of these classes, like interval catch digraphs, interval nest digraphs, adjusted interval digraphs and chronological interval digraphs, are subclasses of the more general class of reflexive interval digraphs -- which arise when we require that the two intervals assigned to a vertex have to intersect. We show that all the problems mentioned above are efficiently solvable, in most of the cases even linear-time solvable, in the class of reflexive interval digraphs, but are APX-hard on even the very restricted class of interval digraphs called point-point digraphs, where the two intervals assigned to each vertex are required to be degenerate, i.e. they consist of a single point each. The results we obtain improve and generalize several existing algorithms and structural results for subclasses of reflexive interval digraphs.
The main goal of this work is to establish a bijection between Dyck words and a family of Eulerian digraphs. We do so by providing two algorithms implementing such bijection in both directions. The connection between Dyck words and Eulerian digraphs exploits a novel combinatorial structure: a binary matrix, we call Dyck matrix, representing the cycles of an Eulerian digraph.
We consider acyclic r-colorings in graphs and digraphs: they color the vertices in r colors, each of which induces an acyclic graph or digraph. (This includes the dichromatic number of a digraph, and the arboricity of a graph.) For any girth and sufficiently high degree, we prove the NP-completeness of acyclic r-colorings; our method also implies the known analogue for classical colorings. The proofs use high girth graphs with high arboricity and dichromatic numbers. High girth graphs and digraphs with high chromatic and dichromatic numbers have been well studied; we re-derive the results from a general result about relational systems, which also implies the similar fact about high girth and high arboricity used in the proofs. These facts concern graphs and digraphs of high girth and low degree; we contrast them by considering acyclic colorings of tournaments (which have low girth and high degree). We prove that even though acyclic two-colorability of tournaments is known to be NP-complete, random acyclically r-colorable tournaments allow recovering an acyclic r-coloring in deterministic linear time, with high probablity.
A circular-arc graph is the intersection graph of arcs of a circle. It is a well-studied graph model with numerous natural applications. A certifying algorithm is an algorithm that outputs a certificate, along with its answer (be it positive or negative), where the certificate can be used to easily justify the given answer. While the recognition of circular-arc graphs has been known to be polynomial since the 1980s, no polynomial-time certifying recognition algorithm is known to date, despite such algorithms being found for many subclasses of circular-arc graphs. This is largely due to the fact that a forbidden structure characterization of circular-arc graphs is not known, even though the problem has been intensely studied since the seminal work of Klee in the 1960s. In this contribution, we settle this problem. We present the first forbidden structure characterization of circular-arc graphs. Our obstruction has the form of mutually avoiding walks in the graph. It naturally extends a similar obstruction that characterizes interval graphs. As a consequence, we give the first polynomial-time certifying algorithm for the recognition of circular-arc graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
