Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userMaximizing the minimum and maximum forcing numbers of perfect matchings of graphs
75
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $G$ be a simple graph with $2n$ vertices and a perfect matching. The forcing number $f(G,M)$ of a perfect matching $M$ of $G$ is the smallest cardinality of a subset of $M$ that is contained in no other perfect matching of $G$. Among all perfect matchings $M$ of $G$, the minimum and maximum values of $f(G,M)$ are called the minimum and maximum forcing numbers of $G$, denoted by $f(G)$ and $F(G)$, respectively. Then $f(G)leq F(G)leq n-1$. Che and Chen (2011) proposed an open problem: how to characterize the graphs $G$ with $f(G)=n-1$. Later they showed that for bipartite graphs $G$, $f(G)=n-1$ if and only if $G$ is complete bipartite graph $K_{n,n}$. In this paper, we solve the problem for general graphs and obtain that $f(G)=n-1$ if and only if $G$ is a complete multipartite graph or $K^+_{n,n}$ ($K_{n,n}$ with arbitrary additional edges in the same partite set). For a larger class of graphs $G$ with $F(G)=n-1$ we show that $G$ is $n$-connected and a brick (3-connected and bicritical graph) except for $K^+_{n,n}$. In particular, we prove that the forcing spectrum of each such graph $G$ is continued by matching 2-switches and the minimum forcing numbers of all such graphs $G$ form an integer interval from $lfloorfrac{n}{2}rfloor$ to $n-1$.
rate research
Read More
Let $G$ be a simple graph with $2n$ vertices and a perfect matching. The forcing number of a perfect matching $M$ of $G$ is the smallest cardinality of a subset of $M$ that is contained in no other perfect matching of $G$. Let $f(G)$ and $F(G)$ denote the minimum and maximum forcing number of $G$ among all perfect matchings, respectively. Hetyei obtained that the maximum number of edges of graphs $G$ with a unique perfect matching is $n^2$ (see Lov{a}sz [20]). We know that $G$ has a unique perfect matching if and only if $f(G)=0$. Along this line, we generalize the classical result to all graphs $G$ with $f(G)=k$ for $0leq kleq n-1$, and obtain that the number of edges is at most $n^2+2nk-k^2-k$ and characterize the extremal graphs as well. Conversely, we get a non-trivial lower bound of $f(G)$ in terms of the order and size. For bipartite graphs, we gain corresponding stronger results. Further, we obtain a new upper bound of $F(G)$. Finally some open problems and conjectures are proposed.
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.
The minimum forcing number of a graph $G$ is the smallest number of edges simultaneously contained in a unique perfect matching of $G$. Zhang, Ye and Shiu cite{HDW} showed that the minimum forcing number of any fullerene graph was bounded below by $3$. However, we find that there exists exactly one excepted fullerene $F_{24}$ with the minimum forcing number $2$. In this paper, we characterize all fullerenes with the minimum forcing number $3$ by a construction approach. This also solves an open problem proposed by Zhang et al. We also find that except for $F_{24}$, all fullerenes with anti-forcing number $4$ have the minimum forcing number $3$. In particular, the nanotube fullerenes of type $(4, 2)$ are such fullerenes.
A family of perfect matchings of $K_{2n}$ is $t$-$intersecting$ if any two members share $t$ or more edges. We prove for any $t in mathbb{N}$ that every $t$-intersecting family of perfect matchings has size no greater than $(2(n-t) - 1)!!$ for sufficiently large $n$, and that equality holds if and only if the family is composed of all perfect matchings that contain a fixed set of $t$ disjoint edges. This is an asymptotic version of a conjecture of Godsil and Meagher that can be seen as the non-bipartite analogue of the Deza-Frankl conjecture proven by Ellis, Friedgut, and Pilpel.
We show that every cubic bridgeless graph with n vertices has at least 3n/4-10 perfect matchings. This is the first bound that differs by more than a constant from the maximal dimension of the perfect matching polytope.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
