共查询到20条相似文献,搜索用时 437 毫秒
1.
2.
For a graph , let denote its number of vertices, its minimum degree and its cycle space. Call a graph Hamilton-generated if and only if every cycle in is a symmetric difference of some Hamilton circuits of . The main purpose of this paper is to prove: for every there exists such that for every graph with vertices,
- (1)if and is odd, then is Hamilton-generated,
- (2)if and is even, then the set of all Hamilton circuits of generates a codimension-one subspace of and the set of all circuits of having length either or generates all of ,
- (3)if and is balanced bipartite, then is Hamilton-generated.
3.
Susan A. van Aardt Christoph Brause Alewyn P. Burger Marietjie Frick Arnfried Kemnitz Ingo Schiermeyer 《Discrete Mathematics》2017,340(11):2673-2677
An edge-coloured graph is called properly connected if any two vertices are connected by a path whose edges are properly coloured. The proper connection number of a connected graph denoted by , is the smallest number of colours that are needed in order to make properly connected. Our main result is the following: Let be a connected graph of order and . If , then except when and where and 相似文献
4.
Let be a set of at least two vertices in a graph . A subtree of is a -Steiner tree if . Two -Steiner trees and are edge-disjoint (resp. internally vertex-disjoint) if (resp. and ). Let (resp. ) be the maximum number of edge-disjoint (resp. internally vertex-disjoint) -Steiner trees in , and let (resp. ) be the minimum (resp. ) for ranges over all -subset of . Kriesell conjectured that if for any , then . He proved that the conjecture holds for . In this paper, we give a short proof of Kriesell’s Conjecture for , and also show that (resp. ) if (resp. ) in , where . Moreover, we also study the relation between and , where is the line graph of . 相似文献
5.
6.
7.
Gentner and Rautenbach conjectured that the size of a minimum zero forcing set in a connected graph on vertices with maximum degree is at most . We disprove this conjecture by constructing a collection of connected graphs with maximum degree 3 of arbitrarily large order having zero forcing number at least . 相似文献
8.
9.
Let be a finite group, written multiplicatively. The Davenport constant of is the smallest positive integer such that every sequence of with elements has a non-empty subsequence with product . Let be the Dihedral Group of order and be the Dicyclic Group of order . Zhuang and Gao (2005) showed that and Bass (2007) showed that . In this paper, we give explicit characterizations of all sequences of such that and is free of subsequences whose product is 1, where is equal to or for some . 相似文献
10.
11.
12.
13.
14.
15.
16.
We say a graph is -colorable with of ’s and of ’s if may be partitioned into independent sets and sets whose induced graphs have maximum degree at most . The maximum average degree, , of a graph is the maximum average degree over all subgraphs of . In this note, for nonnegative integers , we show that if , then is -colorable. 相似文献
17.
A cycle of order is called a -cycle. A non-induced cycle is called a chorded cycle. Let be an integer with . Then a graph of order is chorded pancyclic if contains a chorded -cycle for every integer with . Cream, Gould and Hirohata (Australas. J. Combin. 67 (2017), 463–469) proved that a graph of order satisfying for every pair of nonadjacent vertices , in is chorded pancyclic unless is either or , the Cartesian product of and . They also conjectured that if is Hamiltonian, we can replace the degree sum condition with the weaker density condition
and still guarantee the same conclusion. In this paper, we prove this conjecture by showing that if a graph of order with contains a -cycle, then contains a chorded -cycle, unless and is either or , Then observing that and are exceptions only for , we further relax the density condition for sufficiently large . 相似文献
18.
19.