Results 31 to 40 of about 1,119 (95)
The Dichromatic Number of Infinite Families of Circulant Tournaments
Discussiones Mathematicae Graph Theory, 2017 The dichromatic number dc(D) of a digraph D is defined to be the minimum number of colors such that the vertices of D can be colored in such a way that every chromatic class induces an acyclic subdigraph in D.
Javier Nahid, Llano Bernardo
doaj +1 more source
Forbidden Subgraphs for Collapsible Graphs and Supereulerian Graphs
Discussiones Mathematicae Graph Theory, 2022 In this paper, we completely characterize the connected forbidden subgraphs and pairs of connected forbidden subgraphs that force a 2-edge-connected (2-connected) graph to be collapsible.
Liu Xia, Xiong Liming
doaj +1 more source
Long cycles in certain graphs of large degree
International Journal of Mathematics and Mathematical Sciences, Volume 24, Issue 10, Page 691-697, 2000., 2000 Let G be a connected graph of order n and X = {x ∈ V : d(x) ≥ n/2}. Suppose |X| ≥ 3 and G satisfies the modified Fan′s condition. We show that the vertices of the block B of G containing X form a cycle. This generalizes a result of Fan. We also give an efficient algorithm to obtain such a cycle. The complexity of this algorithm is O(n2). In case G is 2‐
Pak-Ken Wong
wiley +1 more source
Longest cycles in certain bipartite graphs
International Journal of Mathematics and Mathematical Sciences, Volume 21, Issue 1, Page 103-106, 1998., 1995 Let G be a connected bipartite graph with bipartition (X, Y) such that |X| ≥ |Y|(≥2), n = |X| and m = |Y|. Suppose, for all vertices x ∈ X and y ∈ Y, dist(x, y) = 3 implies d(x) + d(y) ≥ n + 1. Then G contains a cycle of length 2m. In particular, if m = n, then G is hamiltomian.
Pak-Ken Wong
wiley +1 more source
Path decompositions of chains and circuits
International Journal of Mathematics and Mathematical Sciences, Volume 6, Issue 3, Page 521-533, 1983., 1983 Expressions for the path polynomials (see Farrell [1]) of chains and circuits are derived. These polynomials are then used to deduce results about node disjoint path decompositions of chains and circuits. Some results are also given for decompositions in which specific paths must be used.
E. J. Farrell
wiley +1 more source
On q-Power Cycles in Cubic Graphs
Discussiones Mathematicae Graph Theory, 2017 In the context of a conjecture of Erdős and Gyárfás, we consider, for any q ≥ 2, the existence of q-power cycles (i.e., with length a power of q) in cubic graphs. We exhibit constructions showing that, for every q ≥ 3, there exist arbitrarily large cubic
Bensmail Julien
doaj +1 more source
A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs
Discussiones Mathematicae Graph Theory, 2016 Let G be a graph on n vertices and let H be a given graph. We say that G is pancyclic, if it contains cycles of all lengths from 3 up to n, and that it is H-f1-heavy, if for every induced subgraph K of G isomorphic to H and every two vertices u, v ∈ V (K)
Wideł Wojciech
doaj +1 more source
Discussiones Mathematicae Graph Theory, 2022 A graph is called Hamiltonian extendable if there exists a Hamiltonian path between any two nonadjacent vertices. In this paper, we give an explicit formula of the minimum number of edges for Hamiltonian extendable graphs and we also characterize the ...
Yang Xiaojing, Xiong Liming
doaj +1 more source
A note on directed 4-cycles in digraphs [PDF]
, 2012 Using some combinatorial techniques, in this note, it is proved that if $\alpha\geq 0.28866$, then any digraph on $n$ vertices with minimum outdegree at least $\alpha n$ contains a directed cycle of length at most ...
Liang, Hao, Xu, Jun-Ming
core
Cyclic Cordial Labeling for the Lemniscate Graphs and Their Second Powers
Journal of Mathematics, Volume 2025, Issue 1, 2025.A lemniscate graph, usually denoted by Ln,m, is defined as a union of two cycles Cn and Cm that share a common vertex. A simple graph is called cyclic group cordial if we can provide a three elements’ cyclic group labeling satisfying certain conditions.
M. A. AbdAllah +4 more
wiley +1 more source