共查询到20条相似文献,搜索用时 11 毫秒
1.
A linear forest is a graph whose connected components are chordless paths. A linear partition of a graph G is a partition of its edge set into linear forests and la(G) is the minimum number of linear forests in a linear partition. It is well known that la(G)=2 when G is a cubic graph and Wormald [N. Wormald, Problem 13, Ars Combinatoria 23(A) (1987) 332-334] conjectured that if |V(G)|≡0 (mod 4), then it is always possible to find a linear partition in two isomorphic linear forests. Here, we give some new results concerning this conjecture. 相似文献
2.
Zsolt Patakfalvi 《Discrete Mathematics》2008,308(12):2351-2365
A graph is called normal if its vertex set can be covered by cliques Q1,Q2,…,Qk and also by stable sets S1,S2,…,Sl, such that Si∩Qj≠∅ for every i,j. This notion is due to Körner, who introduced the class of normal graphs as an extension of the class of perfect graphs. Normality has also relevance in information theory. Here we prove, that the line graphs of cubic graphs are normal. 相似文献
3.
《Discrete Mathematics》2020,343(7):111904
An even cycle decomposition of a graph is a partition of its edges into cycles of even length. In 2012, Markström conjectured that the line graph of every 2-connected cubic graph has an even cycle decomposition and proved this conjecture for cubic graphs with oddness at most 2. However, for 2-connected cubic graphs with oddness 2, Markström only considered these graphs with a chordless 2-factor. (A chordless 2-factor of a graph is a 2-factor consisting of only induced cycles.) In this paper, we first construct an infinite family of 2-connected cubic graphs with oddness 2 and without chordless 2-factors. We then give a complete proof of Markström’s result and further prove this conjecture for cubic graphs with oddness 4. 相似文献
4.
A packing-coloring of a graph is a partition of into sets such that for each the distance between any two distinct is at least . The packing chromatic number, , of a graph is the minimum such that has a packing -coloring. Sloper showed that there are -regular graphs with arbitrarily large packing chromatic number. The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We answer this question in the negative. Moreover, we show that for every fixed and , almost every -vertex cubic graph of girth at least has the packing chromatic number greater than . 相似文献
5.
Let Hn be the number of claw-free cubic graphs on 2n labeled nodes. In an earlier paper we characterized claw-free cubic graphs and derived a recurrence relation for Hn. Here we determine the asymptotic behavior of this sequence:
6.
《Discrete Mathematics》2022,345(11):113113
7.
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. We study lists by three 1‐factors, and call with a ‐core of G. If G is not 3‐edge‐colorable, then . In Steffen (J Graph Theory 78 (2015), 195–206) it is shown that if , then is an upper bound for the girth of G. We show that bounds the oddness of G as well. We prove that . If , then every ‐core has a very specific structure. We call these cores Petersen cores. We show that for any given oddness there is a cyclically 4‐edge‐connected cubic graph G with . On the other hand, the difference between and can be arbitrarily big. This is true even if we additionally fix the oddness. Furthermore, for every integer , there exists a bridgeless cubic graph G such that . 相似文献
8.
We construct a connected cubic nonnormal Cayley graph on for each integer and determine its full automorphism group. This is the first infinite family of connected cubic nonnormal Cayley graphs on nonabelian simple groups. 相似文献
9.
《Discrete Mathematics》2022,345(11):113036
Let G be a cyclically 5-connected cubic graph with a 5-edge-cut separating G into two cyclic components and . We prove that each component can be completed to a cyclically 5-connected cubic graph by adding three vertices, unless is a cycle of length five. Our work extends similar results by Andersen et al. for cyclic connectivity 4 from 1988. 相似文献
10.
We propose three new conjectures on perfect matchings in cubic graphs. The weakest conjecture is implied by a well-known conjecture of Berge and Fulkerson. The other two conjectures are a strengthening of the first one. All conjectures are trivially verified for 3-edge-colorable cubic graphs and by computer for all snarks of order at most 34. 相似文献
11.
《Discrete Mathematics》2020,343(6):111839
The 3-Decomposition Conjecture states that every connected cubic graph can be decomposed into a spanning tree, a 2-regular subgraph and a matching. We prove that this conjecture is true for connected cubic graphs with a 2-factor consisting of three cycles. 相似文献
12.
13.
14.
For a 3-edge-connected cubic graph , we give an algorithm to construct a connected Eulerian subgraph of using at most edges. 相似文献
15.
A set of vertices in a graph is an independent dominating set of if is an independent set and every vertex not in is adjacent to a vertex in . The independent domination number, , of is the minimum cardinality of an independent dominating set. In this paper, we extend the work of Henning, Löwenstein, and Rautenbach (2014) who proved that if is a bipartite, cubic graph of order and of girth at least , then . We show that the bipartite condition can be relaxed, and prove that if is a cubic graph of order and of girth at least , then . 相似文献
16.
Marston Conder Aleksander Malnič Dragan Marušič Primž Potočnik 《Journal of Algebraic Combinatorics》2006,23(3):255-294
A list is given of all semisymmetric (edge- but not vertex-transitive) connected finite cubic graphs of order up to 768. This
list was determined by the authors using Goldschmidt's classification of finite primitive amalgams of index (3,3), and a computer
algorithm for finding all normal subgroups of up to a given index in a finitely-presented group. The list includes several
previously undiscovered graphs. For each graph in the list, a significant amount of information is provided, including its
girth and diameter, the order of its automorphism group, the order and structure of a minimal edge-transitive group of automorphisms,
its Goldschmidt type, stabiliser partitions, and other details about its quotients and covers. A summary of all known infinite
families of semisymmetric cubic graphs is also given, together with explicit rules for their construction, and members of
the list are identified with these. The special case of those graphs having K1,3 as a normal quotient is investigated in detail.
Supported in part by N.Z. Marsden Fund (grant no. UOA 124) and N.Z. Centres of Research Excellence Fund (grant no. UOA 201)
Supported in part by “Ministrstvo za šolstvo, znanost in šport Slovenije”, research program no. 101-506.
Supported in part by research projects no. Z1-4186-0101 and no. Z1-3124-0101. The fourth author would like to thank the University
of Auckland for hospitality during his visit there in 2003. 相似文献
17.
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. 相似文献
18.
Given a graph G=(V,E) and a positive integer k, the partition into cliques (pic) decision problem consists of deciding whether there exists a partition of V into k disjoint subsets V1,V2,…,Vk such that the subgraph induced by each part Vi is a complete subgraph (clique) of G. In this paper, we establish both the NP-completeness of pic for planar cubic graphs and the Max SNP-hardness of pic for cubic graphs. We present a deterministic polynomial time -approximation algorithm for finding clique partitions in maximum degree three graphs. 相似文献
19.
The weak Berge hypothesis states that a graph is perfect if and only if its complement is perfect. Previous proofs of this hypothesis have used combinatorial or polyhedral methods.In this paper, the concept of norms related to graphs is used to provide an alternative proof for the weak Berge hypothesis.This is a written account of an invited lecture delivered by the second author on occasion of the 12. Symposium on Operations Research, Passau, 9.–11. 9. 1987. 相似文献
20.
Michael Tarsi 《Journal of Graph Theory》2020,95(1):138-159
An (r, α)-bounded-excess flow ((r, α)-flow) in an orientation of a graph G = (V, E) is an assignment f : E → [1, r−1], such that for every vertex x ∈ V, . E+(x), respectively E−(x), is the set of edges directed from, respectively toward x. Bounded-excess flows suggest a generalization of Circular nowhere-zero flows (cnzf), which can be regarded as (r, 0)-flows. We define (r, α) as Stronger or equivalent to (s, β), if the existence of an (r, α)-flow in a cubic graph always implies the existence of an (s, β)-flow in the same graph. We then study the structure of the bounded-excess flow strength poset. Among other results, we define the Trace of a point in the r − α plane by and prove that among points with the same trace the stronger is the one with the smaller α (and larger r). For example, if a cubic graph admits a k-nzf (trace k with α = 0), then it admits an -flow for every r, 2 ≤ r ≤ k. A significant part of the article is devoted to proving the main result: Every cubic graph admits a -flow, and there exists a graph which does not admit any stronger bounded-excess flow. Notice that so it can be considered a step in the direction of the 5-flow Conjecture. Our result is the best possible for all cubic graphs while the seemingly stronger 5-flow Conjecture relates only to bridgeless graphs. We also show that if the circular-flow number of a cubic graph is strictly less than 5, then it admits a -flow (trace 4). We conjecture such a flow to exist in every cubic graph with a perfect matching, other than the Petersen graph. This conjecture is a stronger version of the Ban-Linial Conjecture [1]. Our work here strongly relies on the notion of Orientable k-weak bisections, a certain type of k-weak bisections. k-Weak bisections are defined and studied by L. Esperet, G. Mazzuoccolo, and M. Tarsi [4]. 相似文献