Lingjuan Shi ; Heping Zhang - Tight upper bound on the maximum anti-forcing numbers of graphs

dmtcs:3267 - Discrete Mathematics & Theoretical Computer Science, October 17, 2017, Vol. 19 no. 3 -
Tight upper bound on the maximum anti-forcing numbers of graphs

Authors: Lingjuan Shi ; Heping Zhang

    Let $G$ be a simple graph with a perfect matching. Deng and Zhang showed that the maximum anti-forcing number of $G$ is no more than the cyclomatic number. In this paper, we get a novel upper bound on the maximum anti-forcing number of $G$ and investigate the extremal graphs. If $G$ has a perfect matching $M$ whose anti-forcing number attains this upper bound, then we say $G$ is an extremal graph and $M$ is a nice perfect matching. We obtain an equivalent condition for the nice perfect matchings of $G$ and establish a one-to-one correspondence between the nice perfect matchings and the edge-involutions of $G$, which are the automorphisms $\alpha$ of order two such that $v$ and $\alpha(v)$ are adjacent for every vertex $v$. We demonstrate that all extremal graphs can be constructed from $K_2$ by implementing two expansion operations, and $G$ is extremal if and only if one factor in a Cartesian decomposition of $G$ is extremal. As examples, we have that all perfect matchings of the complete graph $K_{2n}$ and the complete bipartite graph $K_{n, n}$ are nice. Also we show that the hypercube $Q_n$, the folded hypercube $FQ_n$ ($n\geq4$) and the enhanced hypercube $Q_{n, k}$ ($0\leq k\leq n-4$) have exactly $n$, $n+1$ and $n+1$ nice perfect matchings respectively.

    Volume: Vol. 19 no. 3
    Section: Graph Theory
    Published on: October 17, 2017
    Accepted on: September 28, 2017
    Submitted on: August 10, 2017
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 565 times.
    This article's PDF has been downloaded 349 times.