اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدStrongly chordal digraphs and $Gamma$-free matrices
77
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We define strongly chordal digraphs, which generalize strongly chordal graphs and chordal bipartite graphs, and are included in the class of chordal digraphs. They correspond to square 0,1 matrices that admit a simultaneous row and column permutation avoiding the {Gamma} matrix. In general, it is not clear if these digraphs can be recognized in polynomial time, and we focus on symmetric digraphs (i.e., graphs with possible loops), tournaments with possible loops, and balanced digraphs. In each of these cases we give a polynomial-time recognition algorithm and a forbidden induced subgraph characterization. We also discuss an algorithm for minimum general dominating set in strongly chordal graphs with possible loops, extending and unifying similar algorithms for strongly chordal graphs and chordal bipartite graphs.
قيم البحث
اقرأ أيضاً
Suppose that D is an acyclic orientation of a graph G. An arc of D is called dependent if its reversal creates a directed cycle. Let m and M denote the minimum and the maximum of the number of dependent arcs over all acyclic orientations of G. We cal
l G fully orientable if G has an acyclic orientation with exactly d dependent arcs for every d satisfying m <= d <= M. A graph G is called chordal if every cycle in G of length at least four has a chord. We show that all chordal graphs are fully orientable.
We introduce a new subclass of chordal graphs that generalizes split graphs, which we call well-partitioned chordal graphs. Split graphs are graphs that admit a partition of the vertex set into cliques that can be arranged in a star structure, the le
aves of which are of size one. Well-partitioned chordal graphs are a generalization of this concept in the following two ways. First, the cliques in the partition can be arranged in a tree structure, and second, each clique is of arbitrary size. We provide a characterization of well-partitioned chordal graphs by forbidden induced subgraphs, and give a polynomial-time algorithm that given any graph, either finds an obstruction, or outputs a partition of its vertex set that asserts that the graph is well-partitioned chordal. We demonstrate the algorithmic use of this graph class by showing that two variants of the problem of finding pairwise disjoint paths between k given pairs of vertices is in FPT parameterized by k on well-partitioned chordal graphs, while on chordal graphs, these problems are only known to be in XP. From the other end, we observe that there are problems that are polynomial-time solvable on split graphs, but become NP-complete on well-partitioned chordal graphs.
The dichromatic number of a digraph $D$ is the minimum number of colors needed to color its vertices in such a way that each color class induces an acyclic digraph. As it generalizes the notion of the chromatic number of graphs, it has been a recent
center of study. In this work we look at possible extensions of Gyarfas-Sumner conjecture. More precisely, we propose as a conjecture a simple characterization of finite sets $mathcal F$ of digraphs such that every oriented graph with sufficiently large dichromatic number must contain a member of $mathcal F$ as an induce subdigraph. Among notable results, we prove that oriented triangle-free graphs without a directed path of length $3$ are $2$-colorable. If condition of triangle-free is replaced with $K_4$-free, then we have an upper bound of $414$. We also show that an orientation of complete multipartite graph with no directed triangle is 2-colorable. To prove these results we introduce the notion of emph{nice sets} that might be of independent interest.
We propose a quantum walk defined by digraphs (mixed graphs). This is like Grover walk that is perturbed by a certain complex-valued function defined by digraphs. The discriminant of this quantum walk is a matrix that is a certain normalization of ge
neralized Hermitian adjacency matrices. Furthermore, we give definitions of the positive and negative supports of the transfer matrix, and clarify explicit formulas of their supports of the square. In addition, we give tables by computer on the identification of digraphs by their eigenvalues.
A cycle $C$ of length $k$ in graph $G$ is extendable if there is another cycle $C$ in $G$ with $V(C) subset V(C)$ and length $k+1$. A graph is cycle extendable if every non-Hamiltonian cycle is extendable. In 1990 Hendry conjectured that any Hamilton
ian chordal graph (a Hamiltonian graph with no induced cycle of length greater than three) is cycle extendable, and this conjecture has been verified for Hamiltonian chordal graphs which are interval graphs, planar graphs, and split graphs. We prove that any 2-connected claw-free chordal graph is cycle extendable.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
