اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدPerfect Forests in Graphs and Their Extensions
77
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $G$ be a graph on $n$ vertices. For $iin {0,1}$ and a connected graph $G$, a spanning forest $F$ of $G$ is called an $i$-perfect forest if every tree in $F$ is an induced subgraph of $G$ and exactly $i$ vertices of $F$ have even degree (including zero). A $i$-perfect forest of $G$ is proper if it has no vertices of degree zero. Scott (2001) showed that every connected graph with even number of vertices contains a (proper) 0-perfect forest. We prove that one can find a 0-perfect forest with minimum number of edges in polynomial time, but it is NP-hard to obtain a 0-perfect forest with maximum number of edges. Moreover, we show that to decide whether $G$ has a 0-perfect forest with at least $|V(G)|/2+k$ edges, where $k$ is the parameter, is W[1]-hard. We also prove that for a prescribed edge $e$ of $G,$ it is NP-hard to obtain a 0-perfect forest containing $e,$ but one can decide if there existsa 0-perfect forest not containing $e$ in polynomial time. It is easy to see that every graph with odd number of vertices has a 1-perfect forest. It is not the case for proper 1-perfect forests. We give a characterization of when a connected graph has a proper 1-perfect forest.
قيم البحث
اقرأ أيضاً
Inspired by applications of perfect graphs in combinatorial optimization, Chv{a}tal defined t-perfect graphs in 1970s. The long efforts of characterizing t-perfect graphs started immediately, but embarrassingly, even a working conjecture on it is sti
ll missing after nearly 50 years. Unlike perfect graphs, t-perfect graphs are not closed under substitution or complementation. A full characterization of t-perfection with respect to substitution has been obtained by Benchetrit in his Ph.D. thesis. Through the present work we attempt to understand t-perfection with respect to complementation. In particular, we show that there are only five pairs of graphs such that both the graphs and their complements are minimally t-imperfect.
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.
Interval graphs were used in the study of genomics by the famous molecular biologist Benzer. Later on probe interval graphs were introduced by Zhang as a generalization of interval graphs for the study of cosmid contig mapping of DNA. A tagged prob
e interval graph (briefly, TPIG) is motivated by similar applications to genomics, where the set of vertices is partitioned into two sets, namely, probes and nonprobes and there is an interval on the real line corresponding to each vertex. The graph has an edge between two probe vertices if their corresponding intervals intersect, has an edge between a probe vertex and a nonprobe vertex if the interval corresponding to a nonprobe vertex contains at least one end point of the interval corresponding to a probe vertex and the set of non-probe vertices is an independent set. This class of graphs have been defined nearly two decades ago, but till today there is no known recognition algorithm for it. In this paper, we consider a natural subclass of TPIG, namely, the class of proper tagged probe interval graphs (in short PTPIG). We present characterization and a linear time recognition algorithm for PTPIG. To obtain this characterization theorem we introduce a new concept called canonical sequence for proper interval graphs, which, we belief, has an independent interest in the study of proper interval graphs. Also to obtain the recognition algorithm for PTPIG, we introduce and solve a variation of consecutive $1$s problem, namely, oriented consecutive $1$s problem and some variations of PQ-tree algorithm. We also discuss the interrelations between the classes of PTPIG and TPIG with probe interval graphs and probe proper interval graphs.
A well-known conjecture by Lovasz and Plummer from the 1970s asserted that a bridgeless cubic graph has exponentially many perfect matchings. It was solved in the affirmative by Esperet et al. (Adv. Math. 2011). On the other hand, Chudnovsky and Seym
our (Combinatorica 2012) proved the conjecture in the special case of cubic planar graphs. In our work we consider random bridgeless cubic planar graphs with the uniform distribution on graphs with $n$ vertices. Under this model we show that the expected number of perfect matchings in labeled bridgeless cubic planar graphs is asymptotically $cgamma^n$, where $c>0$ and $gamma sim 1.14196$ is an explicit algebraic number. We also compute the expected number of perfect matchings in (non necessarily bridgeless) cubic planar graphs and provide lower bounds for unlabeled graphs. Our starting point is a correspondence between counting perfect matchings in rooted cubic planar maps and the partition function of the Ising model in rooted triangulations.
It is an open problem whether the 3-coloring problem can be solved in polynomial time in the class of graphs that do not contain an induced path on $t$ vertices, for fixed $t$. We propose an algorithm that, given a 3-colorable graph without an induce
d path on $t$ vertices, computes a coloring with $max{5,2lceil{frac{t-1}{2}}rceil-2}$ many colors. If the input graph is triangle-free, we only need $max{4,lceil{frac{t-1}{2}}rceil+1}$ many colors. The running time of our algorithm is $O((3^{t-2}+t^2)m+n)$ if the input graph has $n$ vertices and $m$ edges.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
