Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userComplementation in t-perfect graphs
326
0
0.0
(
0
)
Added by
Yixin Cao
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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 still 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.
rate research
Read More
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.
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 Seymour (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.
Let $V$ be a set of cardinality $v$ (possibly infinite). Two graphs $G$ and $G$ with vertex set $V$ are {it isomorphic up to complementation} if $G$ is isomorphic to $G$ or to the complement $bar G$ of $G$. Let $k$ be a non-negative integer, $G$ and $G$ are {it $k$-hypomorphic up to complementation} if for every $k$-element subset $K$ of $V$, the induced subgraphs $G_{restriction K}$ and $G_{restriction K}$ are isomorphic up to complementation. A graph $G$ is {it $k$-reconstructible up to complementation} if every graph $G$ which is $k$-hypomorphic to $G$ up to complementation is in fact isomorphic to $G$ up to complementation. We give a partial characterisation of the set $mathcal S$ of pairs $(n,k)$ such that two graphs $G$ and $G$ on the same set of $n$ vertices are equal up to complementation whenever they are $k$-hypomorphic up to complementation. We prove in particular that $mathcal S$ contains all pairs $(n,k)$ such that $4leq kleq n-4$. We also prove that 4 is the least integer $k$ such that every graph $G$ having a large number $n$ of vertices is $k$-reconstructible up to complementation; this answers a question raised by P. Ille
In this paper we further investigate the well-studied problem of finding a perfect matching in a regular bipartite graph. The first non-trivial algorithm, with running time $O(mn)$, dates back to K{o}nigs work in 1916 (here $m=nd$ is the number of edges in the graph, $2n$ is the number of vertices, and $d$ is the degree of each node). The currently most efficient algorithm takes time $O(m)$, and is due to Cole, Ost, and Schirra. We improve this running time to $O(min{m, frac{n^{2.5}ln n}{d}})$; this minimum can never be larger than $O(n^{1.75}sqrt{ln n})$. We obtain this improvement by proving a uniform sampling theorem: if we sample each edge in a $d$-regular bipartite graph independently with a probability $p = O(frac{nln n}{d^2})$ then the resulting graph has a perfect matching with high probability. The proof involves a decomposition of the graph into pieces which are guaranteed to have many perfect matchings but do not have any small cuts. We then establish a correspondence between potential witnesses to non-existence of a matching (after sampling) in any piece and cuts of comparable size in that same piece. Kargers sampling theorem for preserving cuts in a graph can now be adapted to prove our uniform sampling theorem for preserving perfect matchings. Using the $O(msqrt{n})$ algorithm (due to Hopcroft and Karp) for finding maximum matchings in bipartite graphs on the sampled graph then yields the stated running time. We also provide an infinite family of instances to show that our uniform sampling result is tight up to poly-logarithmic factors (in fact, up to $ln^2 n$).
We prove that, for any $tge 3$, there exists a constant $c=c(t)>0$ such that any $d$-regular $n$-vertex graph with the second largest eigenvalue in absolute value~$lambda$ satisfying $lambdale c d^{t-1}/n^{t-2}$ contains vertex-disjoint copies of $K_t$ covering all but at most $n^{1-1/(8t^4)}$ vertices. This provides further support for the conjecture of Krivelevich, Sudakov and Szabo [emph{Triangle factors in sparse pseudo-random graphs}, Combinatorica textbf{24} (2004), pp.~403--426] that $(n,d,lambda)$-graphs with $nin 3mathbb{N}$ and $lambdaleq cd^{2}/n$ for a suitably small absolute constant~$c>0$ contain triangle-factors.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
