Results 61 to 70 of about 1,699 (154)
Graphs which have pancyclic complements
International Journal of Mathematics and Mathematical Sciences, Volume 1, Issue 2, Page 177-185, 1978., 1978 Let p and q denote the number of vertices and edges of a graph G, respectively. Let Δ(G) denote the maximum degree of G, and G¯ the complement of G. A graph G of order p is said to be pancyclic if G contains a cycle of each length n, 3 ≤ n ≤ p. For a nonnegative integer k, a connected graph G is said to be of rank k if q = p − 1 + k.
H. Joseph Straight
wiley +1 more source
Graphs with at most two moplexes
Journal of Graph Theory, Volume 107, Issue 1, Page 38-69, September 2024.Abstract A moplex is a natural graph structure that arises when lifting Dirac's classical theorem from chordal graphs to general graphs. The notion is known to be closely related to lexicographic searches in graphs as well as to asteroidal triples, and has been applied in several algorithms related to graph classes, such as interval graphs, claw‐free ...
Clément Dallard +4 more
wiley +1 more source
Discrete Applied Mathematics, 2007 A graph \(G\) is said to be geodesic-pancyclic if every path of length \(d\) between any two vertices \(u\) and \(v\) at distance \(d\) (i.e., the shortest path between \(u\) and \(v\)) can be completed to a cycle of length \(\ell\) for every \(\ell=\max\{2d,3\},\dots,n\).
Hung-Chang,C. A. +3 more
openaire +2 more sources
Characterizations of vertex pancyclic and pancyclic ordinary complete multipartite digraphs
Discrete Mathematics, 1995 A digraph is semicomplete if it has no pair of non-adjacent vertices. A semicomplete multipartite digraph is a digraph that can be obtained from some semicomplete digraph \(D\) by choosing a (vertex) spanning collection of vertex disjoint induced subgraphs of \(D\) and deleting all arcs inside each of these.
openaire +6 more sources
A sufficient condition for pre-Hamiltonian cycles in bipartite digraphs
, 2017 Let $D$ be a strongly connected balanced bipartite directed graph of order $2a\geq 10$ other than a directed cycle. Let $x,y$ be distinct vertices in $D$.
Darbinyan, Samvel Kh. +1 more
core +1 more source
The Cycle Spectrum of Claw-free Hamiltonian Graphs [PDF]
, 2013 If $G$ is a claw-free hamiltonian graph of order $n$ and maximum degree $\Delta$ with $\Delta\geq 24$, then $G$ has cycles of at least $\min\left\{ n,\left\lceil\frac{3}{2}\Delta\right\rceil\right\}-2$ many different lengths.Comment: 9 ...
Eckert, Jonas +2 more
core
An upper bound for the crossing number of augmented cubes [PDF]
, 2012 A {\it good drawing} of a graph $G$ is a drawing where the edges are non-self-intersecting and each two edges have at most one point in common, which is either a common end vertex or a crossing.
Wang, Guoqing +4 more
core
Cycles in Random Bipartite Graphs [PDF]
, 2013 In this paper we study cycles in random bipartite graph $G(n,n,p)$. We prove that if $p\gg n^{-2/3}$, then $G(n,n,p)$ a.a.s. satisfies the following. Every subgraph $G'\subset G(n,n,p)$ with more than $(1+o(1))n^2p/2$ edges contains a cycle of length $t$
Shang, Yilun
core
, 2013 We prove that every possible $k$-cycle can be embedded into $PG(n,q)$, for all $n\geq 3$ and $q$ a power of a prime.Comment: 6 ...
Aceves, Elaina +3 more
core +1 more source
A complete classification of which $(n,k)$-star graphs are Cayley graphs
, 2017 The $(n,k)$-star graphs are an important class of interconnection networks that generalize star graphs, which are superior to hypercubes. In this paper, we continue the work begun by Cheng et al.~(Graphs and Combinatorics 2017) and complete the ...
Cheng, Eddie +4 more
core +1 more source