-
Cycles of weight divisible by $k$
Authors:
Ajit A. Diwan
Abstract:
A weighted (directed) graph is a (directed) graph with integer weights assigned to its vertices and edges. The weight of a subgraph is the sum of weights of vertices and edges in the subgraph. The problem of determining the largest order $f(k)$ of a weighted complete directed graph that does not contain a directed cycle of weight divisible by $k$, for an integer $k \ge 2$, was raised by Alon and K…
▽ More
A weighted (directed) graph is a (directed) graph with integer weights assigned to its vertices and edges. The weight of a subgraph is the sum of weights of vertices and edges in the subgraph. The problem of determining the largest order $f(k)$ of a weighted complete directed graph that does not contain a directed cycle of weight divisible by $k$, for an integer $k \ge 2$, was raised by Alon and Krivelevich [J. Graph Theory 98 (2021) 623-629]. They showed that $f(k)$ is $O(k\log k)$ and $f(k) \le 2k-2$ if $k$ is prime. The best bounds known to us are $f(k) \le 2k-2$ for all $k$ and $f(k) < (3k-1)/2$ for prime $k$. It is also known that $f(k) \ge k$ and this is believed to be the correct value. We prove that $f(k) < k+2Ω(k)$, where $Ω(k)$ is the number of prime factors, not necessarily distinct, in the prime factorization of $k$.
We also show that any weighted undirected graph of minimum degree $2k-1$ contains a cycle of weight divisible by $k$. This result is proved in the more general setting in which the weights are from a finite abelian group of order $k$, and the cycle has weight equal to the group identity. We conjecture that this holds for undirected graphs with minimum degree $k+1$.
△ Less
Submitted 1 July, 2024;
originally announced July 2024.
-
Planar Cycle-Extendable Graphs
Authors:
Aditya Y Dalwadi,
Kapil R Shenvi Pause,
Ajit A Diwan,
Nishad Kothari
Abstract:
For most problems pertaining to perfect matchings, one may restrict attention to matching covered graphs -- that is, connected nontrivial graphs with the property that each edge belongs to some perfect matching. There is extensive literature on these graphs that are also known as $1$-extendable graphs (since each edge extends to a perfect matching) including an ear decomposition theorem due to Lov…
▽ More
For most problems pertaining to perfect matchings, one may restrict attention to matching covered graphs -- that is, connected nontrivial graphs with the property that each edge belongs to some perfect matching. There is extensive literature on these graphs that are also known as $1$-extendable graphs (since each edge extends to a perfect matching) including an ear decomposition theorem due to Lovasz and Plummer.
A cycle $C$ of a graph $G$ is conformal if $G-V(C)$ has a perfect matching; such cycles play an important role in the study of perfect matchings, especially when investigating the Pfaffian orientation problem. A matching covered graph $G$ is cycle-extendable if -- for each even cycle $C$ -- the cycle $C$ is conformal, or equivalently, each perfect matching of $C$ extends to a perfect matching of $G$, or equivalently, $C$ is the symmetric difference of two perfect matchings of $G$, or equivalently, $C$ extends to an ear decomposition of $G$. In the literature, these are also known as cycle-nice or as $1$-cycle resonant graphs.
Zhang, Wang, Yuan, Ng and Cheng [Discrete Mathematics, 345:7 (2022), 112876] provided a characterization of claw-free cycle-extendable graphs. Guo and Zhang [Discrete Mathematics, 275:1-3 (2004), 151-164] and independently Zhang and Li [Discrete Applied Mathematics, 160:13-14 (2012), 2069-2074], provided characterizations of bipartite planar cycle-extendable graphs. In this paper, we establish a characterization of all planar cycle-extendable graphs -- in terms of $K_2$ and four infinite families.
△ Less
Submitted 6 July, 2024; v1 submitted 24 May, 2024;
originally announced May 2024.
-
Extremal minimal bipartite matching covered graphs
Authors:
Amit Kumar Mallik,
Ajit A. Diwan,
Nishad Kothari
Abstract:
A connected graph, on four or more vertices, is matching covered if every edge is present in some perfect matching. An ear decomposition theorem (similar to the one for $2$-connected graphs) exists for bipartite matching covered graphs due to Hetyei. From the results and proofs of Lovász and Plummer, that rely on Hetyei's theorem, one may deduce that any minimal bipartite matching covered graph ha…
▽ More
A connected graph, on four or more vertices, is matching covered if every edge is present in some perfect matching. An ear decomposition theorem (similar to the one for $2$-connected graphs) exists for bipartite matching covered graphs due to Hetyei. From the results and proofs of Lovász and Plummer, that rely on Hetyei's theorem, one may deduce that any minimal bipartite matching covered graph has at least $2(m-n+2)$ vertices of degree two (where minimal means that deleting any edge results in a graph that is not matching covered); such a graph is said to be extremal if it attains the stated lower bound.
In this paper, we provide a complete characterization of the class of extremal minimal bipartite matching covered graphs. In particular, we prove that every such graph $G$ is obtained from two copies of a tree devoid of degree two vertices, say $T$ and $T'$, by adding edges -- each of which joins a leaf of $T$ with the corresponding leaf of $T'$.
Apart from the aforementioned bound, there are four other bounds that appear in, or may be deduced from, the work of Lovász and Plummer. Each of these bounds leads to a notion of extremality. In this paper, we obtain a complete characterization of all of these extremal classes and also establish relationships between them. Two of our characterizations are in the same spirit as the one stated above. For the remaining two extremal classes, we reduce each of them to one of the already characterized extremal classes using standard matching theoretic operations.
△ Less
Submitted 11 April, 2024; v1 submitted 9 April, 2024;
originally announced April 2024.
-
Subdivisions of maximal 3-degenerate graphs of order $d+1$ in graphs of minimum degree $d$
Authors:
Ajit A. Diwan
Abstract:
We prove that every graph of minimum degree at least $d \ge 1$ contains a subdivision of some maximal 3-degenerate graph of order $d+1$. This generalizes the classic results of Dirac ($d=3$) and Pelikán ($d=4$). We conjecture that for any planar maximal 3-degenerate graph $H$ of order $d+1$ and any graph $G$ of minimum degree at least $d$, $G$ contains a subdivision of $H$. We verify this in the c…
▽ More
We prove that every graph of minimum degree at least $d \ge 1$ contains a subdivision of some maximal 3-degenerate graph of order $d+1$. This generalizes the classic results of Dirac ($d=3$) and Pelikán ($d=4$). We conjecture that for any planar maximal 3-degenerate graph $H$ of order $d+1$ and any graph $G$ of minimum degree at least $d$, $G$ contains a subdivision of $H$. We verify this in the case $H$ is $P_6^3$ and $P_7^3$
△ Less
Submitted 18 April, 2020;
originally announced April 2020.
-
The minimum forcing number of perfect matchings in the hypercube
Authors:
Ajit A. Diwan
Abstract:
Let $M$ be a perfect matching in a graph. A subset $S$ of $M$ is said to be a forcing set of $M$, if $M$ is the only perfect matching in the graph that contains $S$. The minimum size of a forcing set of $M$ is called the forcing number of $M$. Pachter and Kim [Discrete Math. 190 (1998) 287--294] conjectured that the forcing number of every perfect matching in the $n$-dimensional hypercube is at le…
▽ More
Let $M$ be a perfect matching in a graph. A subset $S$ of $M$ is said to be a forcing set of $M$, if $M$ is the only perfect matching in the graph that contains $S$. The minimum size of a forcing set of $M$ is called the forcing number of $M$. Pachter and Kim [Discrete Math. 190 (1998) 287--294] conjectured that the forcing number of every perfect matching in the $n$-dimensional hypercube is at least $2^{n-2}$, for all $n \ge 2$. Riddle [Discrete Math. 245 (2002) 283-292] proved this for even $n$. We show that the conjecture holds for all $n \ge 2$. The proof is based on simple linear algebra.
△ Less
Submitted 10 December, 2017;
originally announced December 2017.
-
Four-connected triangulations of planar point sets
Authors:
Ajit Arvind Diwan,
Subir Kumar Ghosh,
Bodhayan Roy
Abstract:
In this paper, we consider the problem of determining in polynomial time whether a given planar point set $P$ of $n$ points admits 4-connected triangulation. We propose a necessary and sufficient condition for recognizing $P$, and present an $O(n^3)$ algorithm of constructing a 4-connected triangulation of $P$. Thus, our algorithm solves a longstanding open problem in computational geometry and ge…
▽ More
In this paper, we consider the problem of determining in polynomial time whether a given planar point set $P$ of $n$ points admits 4-connected triangulation. We propose a necessary and sufficient condition for recognizing $P$, and present an $O(n^3)$ algorithm of constructing a 4-connected triangulation of $P$. Thus, our algorithm solves a longstanding open problem in computational geometry and geometric graph theory. We also provide a simple method for constructing a noncomplex triangulation of $P$ which requires $O(n^2)$ steps. This method provides a new insight to the structure of 4-connected triangulation of point sets.
△ Less
Submitted 7 October, 2013;
originally announced October 2013.
-
A sufficient condition for the existence of an anti-directed 2-factor in a directed graph
Authors:
Ajit A. Diwan,
Josh B. Frye,
Michael J. Plantholt,
Shailesh K. Tipnis
Abstract:
Let D be a directed graph with vertex set V and order n. An anti-directed hamiltonian cycle H in D is a hamiltonian cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. An anti-directed 2-factor in D is a vertex-disjoint collection of anti-directed cycles in D that span V. It was proved in [3] that if the indegree and the outdegree of each vertex of…
▽ More
Let D be a directed graph with vertex set V and order n. An anti-directed hamiltonian cycle H in D is a hamiltonian cycle in the graph underlying D such that no pair of consecutive arcs in H form a directed path in D. An anti-directed 2-factor in D is a vertex-disjoint collection of anti-directed cycles in D that span V. It was proved in [3] that if the indegree and the outdegree of each vertex of D is greater than (9/16)n then D contains an anti-directed hamilton cycle. In this paper we prove that given a directed graph D, the problem of determining whether D has an anti-directed 2-factor is NP-complete, and we use a proof technique similar to the one used in [3] to prove that if the indegree and the outdegree of each vertex of D is greater than (24/46)n then D contains an anti-directed 2-factor.
△ Less
Submitted 21 February, 2011; v1 submitted 6 December, 2010;
originally announced December 2010.
