Nowhere‐Zero 5‐Flows On Cubic Graphs with Oddness 4

Tutte's 5‐flow conjecture from 1954 states that every bridgeless graph has a nowhere‐zero 5‐flow. It suffices to prove the conjecture for cyclically 6‐edge‐connected cubic graphs. We prove that every cyclically 6‐edge‐connected cubic graph with oddness at most 4 has a nowhere‐zero 5‐flow. This implies that every minimum counterexample to the 5‐flow conjecture has oddness at least 6.     

On Cubic Bridgeless Graphs Whose Edge‐Set Cannot be Covered by Four Perfect Matchings

The problem of establishing the number of perfect matchings necessary to cover the edge‐set of a cubic bridgeless graph is strictly related to a famous conjecture of Berge and Fulkerson. In this article, we prove that deciding whether this number is at most four for a given cubic bridgeless graph is NP‐complete. We also construct an infinite family of snarks (cyclically 4‐edge‐connected cubic graphs of girth at least 5 and chromatic index 4) whose edge‐set cannot be covered by four perfect matchings. Only two such graphs were known. It turns out that the family also has interesting properties with respect to the shortest cycle cover problem. The shortest cycle cover of any cubic bridgeless graph with m edges has length at least , and we show that this inequality is strict for graphs of . We also construct the first known snark with no cycle cover of length less than .     

关于3正则图的三匹配交猜想(Ⅱ)

Fan和Raspaud 1994年提出如下猜想：任一无桥3正则图必有三个交为空集的完美匹配．本文证明了如下结果：若G是一个圈4-边连通的无桥3正则图，且存在G的一个完美匹配M1使得G—M1恰为4个奇圈的不交并，则存在图G的两个完美匹配M2和M3使得M1∩M2∩M3=Φ。     

原始图与三次图的可圈度

本文综述关于原始图与三次图的可圈度的近期结果并提出一些未解决的问题。     

Graphs with independent perfect matchings

A graph with at least two vertices is matching covered if it is connected and each edge lies in some perfect matching. A matching covered graph G is extremal if the number of perfect matchings of G is equal to the dimension of the lattice spanned by the set of incidence vectors of perfect matchings of G. We first establish several basic properties of extremal matching covered graphs. In particular, we show that every extremal brick may be obtained by splicing graphs whose underlying simple graphs are odd wheels. Then, using the main theorem proved in 2 and 3 , we find all the extremal cubic matching covered graphs. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 19–50, 2005     

Antimagic Labeling of Cubic Graphs

An antimagic labeling of a graph G is a one‐to‐one correspondence between and such that the sum of the labels assigned to edges incident to distinct vertices are different. If G has an antimagic labeling, then we say G is antimagic. This article proves that cubic graphs are antimagic.     

Paired-Domination in Claw-Free Cubic Graphs

A set S of vertices in a graph G is a paired-dominating set of G if every vertex of G is adjacent to some vertex in S and if the subgraph induced by S contains a perfect matching. The minimum cardinality of a paired-dominating set of G is the paired-domination number of G, denoted by _pr(G). If G does not contain a graph F as an induced subgraph, then G is said to be F-free. In particular if F=K_1,3 or K₄–e, then we say that G is claw-free or diamond-free, respectively. Let G be a connected cubic graph of order n. We show that (i) if G is (K_1,3,K₄–e,C₄)-free, then _pr(G)3n/8; (ii) if G is claw-free and diamond-free, then _pr(G)2n/5; (iii) if G is claw-free, then _pr(G)n/2. In all three cases, the extremal graphs are characterized.Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal. This paper was written while the second author was visiting the Laboratoire de Recherche en Informatique (LRI) at the Université de Paris-Sud in July 2002. The second author thanks the LRI for their warm hospitality     

上连通和超连通的三次Bi-Cayley图

Let G be a finite group and let S(possibly, contains the identity element) be a subset of G. The Bi-Cayley graph BC(G, S) is a bipartite graph with vertex set G×{0, 1} and edge set {(g, 0) (sg, 1) : g∈G, s ∈ S}. A graph is said to be super-connected if every minimum vertex cut isolates a vertex. A graph is said to be hyper-connected if every minimum vertex cut creates two components, one of which is an isolated vertex. In this paper, super-connected and/or hyper-connected cubic Bi-Cayley graphs are characterized.     

上连通和超连通三次点传递图

图G称为上连通的,若对每个最小割集C,G-C有孤立点,G称为超连通的,若对每个最小割集C,G-C恰有两个连通分支,且其中之一为弧立点,本文刻划了上连通和超连通三次点传递图。     

Minimum Power Dominating Sets of Random Cubic Graphs

We present two heuristics for finding a small power dominating set of cubic graphs. We analyze the performance of these heuristics on random cubic graphs using differential equations. In this way, we prove that the proportion of vertices in a minimum power dominating set of a random cubic graph is asymptotically almost surely at most 0.067801. We also provide a corresponding lower bound of using known results on bisection width.     

Oddness to resistance ratios in cubic graphs

Let $G$ be a bridgeless cubic graph. Oddness (weak oddness) is defined as the minimum number of odd components in a 2-factor (an even factor) of $G$, denoted as $\omega \left(G\right)$ (Steffen, 2004) (${\omega }^{\prime }\left(G\right)$ Lukot’ka and Mazák (2016)). Oddness and weak oddness have been referred to as measurements of uncolourability (Fiol et al., 2017, Lukot’ka and Mazák, 2016, Lukot’ka et al., 2015 and, Steffen, 2004), due to the fact that $\omega \left(G\right)=0$ and ${\omega }^{\prime }\left(G\right)=0$ if and only if $G$ is 3-edge-colourable. Another so-called measurement of uncolourability is resistance, defined as the minimum number of edges that can be removed from $G$ such that the resulting graph is 3-edge-colourable, denoted as $r\left(G\right)$ (Steffen, 2004). It is easily shown that $\omega \left(G\right)\ge {\omega }^{\prime }\left(G\right)\ge r\left(G\right)$. While it has been shown that the difference between any two of these measures can be arbitrarily large, it has been conjectured that ${\omega }^{\prime }\left(G\right)\le 2r\left(G\right)$, and that if $G$ is a snark then $\omega \left(G\right)\le 2r\left(G\right)$ (Fiol et al., 2017). In this paper, we disprove the latter by showing that the ratio of oddness to weak oddness can be arbitrarily large. We also offer some insights into the former conjecture by defining what we call resistance reducibility, and hypothesizing that almost all cubic graphs are such resistance reducible.     

Flows and Bisections in Cubic Graphs

A k‐weak bisection of a cubic graph G is a partition of the vertex‐set of G into two parts V₁ and V₂ of equal size, such that each connected component of the subgraph of G induced by () is a tree of at most vertices. This notion can be viewed as a relaxed version of nowhere‐zero flows, as it directly follows from old results of Jaeger that every cubic graph G with a circular nowhere‐zero r‐flow has a ‐weak bisection. In this article, we study problems related to the existence of k‐weak bisections. We believe that every cubic graph that has a perfect matching, other than the Petersen graph, admits a 4‐weak bisection and we present a family of cubic graphs with no perfect matching that do not admit such a bisection. The main result of this article is that every cubic graph admits a 5‐weak bisection. When restricted to bridgeless graphs, that result would be a consequence of the assertion of the 5‐flow Conjecture and as such it can be considered a (very small) step toward proving that assertion. However, the harder part of our proof focuses on graphs that do contain bridges.     

Independent Domination in Cubic Graphs

A set S of vertices in a graph G is an independent dominating set of G if S is an independent set and every vertex not in S is adjacent to a vertex in S. The independent domination number of G, denoted by , is the minimum cardinality of an independent dominating set. In this article, we show that if is a connected cubic graph of order n that does not have a subgraph isomorphic to K_{2, 3}, then . As a consequence of our main result, we deduce Reed's important result [Combin Probab Comput 5 (1996), 277–295] that if G is a cubic graph of order n, then , where denotes the domination number of G.     

1‐Factor and Cycle Covers of Cubic Graphs

Let G be a bridgeless cubic graph. Consider a list of k 1‐factors of G. Let be the set of edges contained in precisely i members of the k 1‐factors. Let be the smallest over all lists of k 1‐factors of G. Any list of three 1‐factors induces a core of a cubic graph. We use results on the structure of cores to prove sufficient conditions for Berge‐covers and for the existence of three 1‐factors with empty intersection. Furthermore, if , then is an upper bound for the girth of G. We also prove some new upper bounds for the length of shortest cycle covers of bridgeless cubic graphs. Cubic graphs with have a 4‐cycle cover of length and a 5‐cycle double cover. These graphs also satisfy two conjectures of Zhang 18 . We also give a negative answer to a problem stated in 18 .     

The equivalence of two conjectures of Berge and Fulkerson

Let G be a bridgeless cubic graph. Fulkerson conjectured that there exist six 1‐factors of G such that each edge of G is contained in exactly two of them. Berge conjectured that the edge‐set of G can be covered with at most five 1‐factors. We prove that the two conjectures are equivalent. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:125‐128, 2011     

On the Intersection Number of Matchings and Minimum Weight Perfect Matchings of Multicolored Point Sets

Let P and Q be disjoint point sets with 2r and 2s elements respectively, and M₁ and M₂ be their minimum weight perfect matchings (with respect to edge lengths). We prove that the edges of M₁ and M₂ intersect at most |M₁|+|M₂|−1 times. This bound is tight. We also prove that P and Q have perfect matchings (not necessarily of minimum weight) such that their edges intersect at most min{r,s} times. This bound is also sharp. Supported by PAPIIT(UNAM) of México, Proyecto IN110802 Supported by FAI-UASLP and by CONACYT of México, Proyecto 32168-E Supported by CONACYT of México, Proyecto 37540-A     

Cycles Containing a Subset of a Given Set of Elements in Cubic Graphs

The technique of contractions and the known results in the study of cycles in $3$-connected cubic graphs are applied to obtain the following result. Let $G$ be a $3$-connected cubic graph, $X\subseteq V(G)$ with $|X| = 16$ and $e\in E(G)$. Then either for every $8$-subset $A$ of $X$, $A\cup\{e\}$ is cyclable or for some $14$-subset $A$ of $X$, $A\cup\{e\}$ is cyclable.     

Random perfect matchings in regular graphs

We prove that in all regular robust expanders $G$, every edge is asymptotically equally likely contained in a uniformly chosen perfect matching $M$. We also show that given any fixed matching or spanning regular graph $N$ in $G$, the random variable $|M\cap E(N)|$ is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders.     

Small maximal matchings of random cubic graphs

We consider the expected size of a smallest maximal matching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs. We analyze the average‐case performance of this heuristic on random n‐vertex cubic graphs using differential equations. In this way, we prove that the expected size of the maximal matching returned by the algorithm is asymptotically almost surely (a.a.s.) less than 0.34623n. We also give an existence proof which shows that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. less than 0.3214n. It is known that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. larger than 0.3158n. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 293–323, 2009