The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Displaying similar documents to “Hamiltonicity of cubic Cayley graphs”

Spectral radius and Hamiltonicity of graphs with large minimum degree

Vladimir Nikiforov (2016)

Czechoslovak Mathematical Journal

Similarity:

Let G be a graph of order n and λ ( G ) the spectral radius of its adjacency matrix. We extend some recent results on sufficient conditions for Hamiltonian paths and cycles in G . One of the main results of the paper is the following theorem: Let k 2 , n k 3 + k + 4 , and let G be a graph of order n , with minimum degree δ ( G ) k . If λ ( G ) n - k - 1 , then G has a Hamiltonian cycle, unless G = K 1 ( K n - k - 1 + K k ) or G = K k ( K n - 2 k + K ¯ k ) .

On short cycles in triangle-free oriented graphs

Yurong Ji, Shufei Wu, Hui Song (2018)

Czechoslovak Mathematical Journal

Similarity:

An orientation of a simple graph is referred to as an oriented graph. Caccetta and Häggkvist conjectured that any digraph on n vertices with minimum outdegree d contains a directed cycle of length at most n / d . In this paper, we consider short cycles in oriented graphs without directed triangles. Suppose that α 0 is the smallest real such that every n -vertex digraph with minimum outdegree at least α 0 n contains a directed triangle. Let ϵ < ( 3 - 2 α 0 ) / ( 4 - 2 α 0 ) be a positive real. We show that if D is an oriented graph...

The Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths

Halina Bielak, Kinga Dąbrowska (2015)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

The Ramsey number R ( G , H ) for a pair of graphs G and H is defined as the smallest integer n such that, for any graph F on n vertices, either F contains G or F ¯ contains H as a subgraph, where F ¯ denotes the complement of F . We study Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths and determine these numbers for some cases. We extend many known results studied in [5, 14, 18, 19, 20]. In particular we count the numbers R ( K 1 + L n , P m ) and R ( K 1 + L n , C m ) for some integers m , n , where L n is...

Acyclic 4-choosability of planar graphs without 4-cycles

Yingcai Sun, Min Chen (2020)

Czechoslovak Mathematical Journal

Similarity:

A proper vertex coloring of a graph G is acyclic if there is no bicolored cycle in G . In other words, each cycle of G must be colored with at least three colors. Given a list assignment L = { L ( v ) : v V } , if there exists an acyclic coloring π of G such that π ( v ) L ( v ) for all v V , then we say that G is acyclically L -colorable. If G is acyclically L -colorable for any list assignment L with | L ( v ) | k for all v V , then G is acyclically k -choosable. In 2006, Montassier, Raspaud and Wang conjectured that every planar graph without...

Degree sums of adjacent vertices for traceability of claw-free graphs

Tao Tian, Liming Xiong, Zhi-Hong Chen, Shipeng Wang (2022)

Czechoslovak Mathematical Journal

Similarity:

The line graph of a graph G , denoted by L ( G ) , has E ( G ) as its vertex set, where two vertices in L ( G ) are adjacent if and only if the corresponding edges in G have a vertex in common. For a graph H , define σ ¯ 2 ( H ) = min { d ( u ) + d ( v ) : u v E ( H ) } . Let H be a 2-connected claw-free simple graph of order n with δ ( H ) 3 . We show that, if σ ¯ 2 ( H ) 1 7 ( 2 n - 5 ) and n is sufficiently large, then either H is traceable or the Ryjáček’s closure cl ( H ) = L ( G ) , where G is an essentially 2 -edge-connected triangle-free graph that can be contracted to one of the two graphs of order 10...

The Turán number of the graph 3 P 4

Halina Bielak, Sebastian Kieliszek (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

Let e x ( n , G ) denote the maximum number of edges in a graph on n vertices which does not contain G as a subgraph. Let P i denote a path consisting of i vertices and let m P i denote m disjoint copies of P i . In this paper we count e x ( n , 3 P 4 ) .

Saturation numbers for linear forests P 6 + t P 2

Jingru Yan (2023)

Czechoslovak Mathematical Journal

Similarity:

A graph G is H -saturated if it contains no H as a subgraph, but does contain H after the addition of any edge in the complement of G . The saturation number, sat ( n , H ) , is the minimum number of edges of a graph in the set of all H -saturated graphs of order n . We determine the saturation number sat ( n , P 6 + t P 2 ) for n 10 3 t + 10 and characterize the extremal graphs for n > 10 3 t + 20 .

Even factor of bridgeless graphs containing two specified edges

Nastaran Haghparast, Dariush Kiani (2018)

Czechoslovak Mathematical Journal

Similarity:

An even factor of a graph is a spanning subgraph in which each vertex has a positive even degree. Let G be a bridgeless simple graph with minimum degree at least 3 . Jackson and Yoshimoto (2007) showed that G has an even factor containing two arbitrary prescribed edges. They also proved that G has an even factor in which each component has order at least four. Moreover, Xiong, Lu and Han (2009) showed that for each pair of edges e 1 and e 2 of G , there is an even factor containing e 1 and e 2 ...

Resolving sets of directed Cayley graphs for the direct product of cyclic groups

Demelash Ashagrie Mengesha, Tomáš Vetrík (2019)

Czechoslovak Mathematical Journal

Similarity:

A directed Cayley graph C ( Γ , X ) is specified by a group Γ and an identity-free generating set X for this group. Vertices of C ( Γ , X ) are elements of Γ and there is a directed edge from the vertex u to the vertex v in C ( Γ , X ) if and only if there is a generator x X such that u x = v . We study graphs C ( Γ , X ) for the direct product Z m × Z n of two cyclic groups Z m and Z n , and the generating set X = { ( 0 , 1 ) , ( 1 , 0 ) , ( 2 , 0 ) , , ( p , 0 ) } . We present resolving sets which yield upper bounds on the metric dimension of these graphs for p = 2 and 3 .

A note on solvable vertex stabilizers of s -transitive graphs of prime valency

Song-Tao Guo, Hailong Hou, Yong Xu (2015)

Czechoslovak Mathematical Journal

Similarity:

A graph X , with a group G of automorphisms of X , is said to be ( G , s ) -transitive, for some s 1 , if G is transitive on s -arcs but not on ( s + 1 ) -arcs. Let X be a connected ( G , s ) -transitive graph of prime valency p 5 , and G v the vertex stabilizer of a vertex v V ( X ) . Suppose that G v is solvable. Weiss (1974) proved that | G v | p ( p - 1 ) 2 . In this paper, we prove that G v ( p m ) × n for some positive integers m and n such that n div m and m p - 1 .

Generalized 3-edge-connectivity of Cartesian product graphs

Yuefang Sun (2015)

Czechoslovak Mathematical Journal

Similarity:

The generalized k -connectivity κ k ( G ) of a graph G was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k -edge-connectivity which is defined as λ k ( G ) = min { λ ( S ) : S V ( G ) and | S | = k } , where λ ( S ) denotes the maximum number of pairwise edge-disjoint trees T 1 , T 2 , ... , T in G such that S V ( T i ) for 1 i . In this paper we prove that for any two connected graphs G and H we have λ 3 ( G H ) λ 3 ( G ) + λ 3 ( H ) , where G H is the Cartesian product of G and H . Moreover, the bound is sharp. We also...