Results 51 to 60 of about 144 (108)
Cyclic Permutations in Determining Crossing Numbers
Discussiones Mathematicae Graph Theory, 2022 The crossing number of a graph G is the minimum number of edge crossings over all drawings of G in the plane. Recently, the crossing numbers of join products of two graphs have been studied.
Klešč Marián, Staš Michal
doaj +1 more source
Dirac type condition and Hamiltonian graphs [PDF]
, 2011 2010 Mathematics Subject Classification: 05C38, 05C45.In 1952, Dirac introduced the degree type condition and proved that if G is a connected graph of order n і 3 such that its minimum degree satisfies d(G) і n/2, then G is Hamiltonian.
Zhao, Kewen
core
The Complexity of Recognizing Tough Cubic Graphs
, 1997 We show that it is NP-hard to determine if a cubic graph G is 1-tough. We then use this result to show that for any integer t # 1, it is NP-hard to determine if a 3 t-regular graph is t-tough. We conclude with some remarks concerning the complexity of
D. Bauer +7 more
core +1 more source
Enumeration of weighted paths on a digraph and block hook determinant
Special Matrices, 2021 In this article, we evaluate determinants of “block hook” matrices, which are block matrices consist of hook matrices. In particular, we deduce that the determinant of a block hook matrix factorizes nicely.
Bera Sudip
doaj +1 more source
Biclique Decompositions and Hermitian Rank
, 1999 The Hermitian rank, h(A), of a Hermitian matrix A is defined and shown to equal maxfn+ (A); n \Gamma (A)g, the maximum of the numbers of positive and negative eigenvalues of A.
Valerie L. Watts +6 more
core +1 more source
On the Number of Disjoint 4-Cycles in Regular Tournaments
Discussiones Mathematicae Graph Theory, 2018 In this paper, we prove that for an integer r ≥ 1, every regular tournament T of degree 3r − 1 contains at least 2116r-103${{21} \over {16}}r - {{10} \over 3}$ disjoint directed 4-cycles. Our result is an improvement of Lichiardopol’s theorem when taking
Ma Fuhong, Yan Jin
doaj +1 more source
Forbidden Pairs and (k,m)-Pancyclicity
Discussiones Mathematicae Graph Theory, 2017 A graph G on n vertices is said to be (k, m)-pancyclic if every set of k vertices in G is contained in a cycle of length r for each r ∈ {m, m+1, . . . , n}.
Crane Charles Brian
doaj +1 more source
On the n-Partite Tournaments with Exactly n − m + 1 Cycles of Length m
Discussiones Mathematicae Graph Theory, 2021 Gutin and Rafiey [Multipartite tournaments with small number of cycles, Australas J. Combin. 34 (2006) 17–21] raised the following two problems: (1) Let m ∈ {3, 4, . . ., n}.
Guo Qiaoping, Meng Wei
doaj +1 more source
Removable Edges on a Hamilton Cycle or Outside a Cycle in a 4-Connected Graph
Discussiones Mathematicae Graph Theory, 2021 Let G be a 4-connected graph. We call an edge e of G removable if the following sequence of operations results in a 4-connected graph: delete e from G; if there are vertices with degree 3 in G− e, then for each (of the at most two) such vertex x, delete ...
Wu Jichang +3 more
doaj +1 more source
, 1999 . Replace certain edges of a directed graph by chains and consider the eect on the spectrum of the graph. It is shown that the spectral radius decreases monotonically with the expansion and that, for a strongly connected graph that is not a single cycle,
Hans Schneider +2 more
core +1 more source