Results 41 to 50 of about 105 (94)
Old and new generalizations of line graphs
International Journal of Mathematics and Mathematical Sciences, Volume 2004, Issue 29, Page 1509-1521, 2004., 2004 Line graphs have been studied for over seventy years. In 1932, H. Whitney showed that for connected graphs, edge‐isomorphism implies isomorphism except for K3 and K1,3. The line graph transformation is one of the most widely studied of all graph transformations.
Jay Bagga
wiley +1 more source
A Triple of Heavy Subgraphs Ensuring Pancyclicity of 2-Connected Graphs
Discussiones Mathematicae Graph Theory, 2017 A graph G on n vertices is said to be pancyclic if it contains cycles of all lengths k for k ∈ {3, . . . , n}. A vertex v ∈ V (G) is called super-heavy if the number of its neighbours in G is at least (n+1)/2.
Wide Wojciech
doaj +1 more source
Journal of Combinatorial Theory, Series B, 1971 AbstractA graph G with vertex set V(G) and edge set E(G) is pancyclic if it contains cycles of all lengths l, 3 ≤ l ≤ | V(G) |.Theorem. Let G be Hamiltonian and suppose that |E(G)| ≥ n24, where n = |V(G)|. Then G is either pancyclic or else is the complete bipartite graph Kn2,n2.As a corollary to this theorem it is shown that the Ore conditions for a ...
openaire +1 more source
Chvátal-Erdo ̋s condition for pancyclicity
Journal of the Association for Mathematical Research, 2023 An n-vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices and it is pancyclic if it contains cycles of all lengths from 3 up to n. A celebrated meta-conjecture of Bondy states that every non-trivial condition implying Hamiltonicity also implies pancyclicity (up to possibly a few exceptional graphs).
Draganić, Nemanja +2 more
openaire +3 more sources
The Completion Numbers of Hamiltonicity and Pancyclicity in Random Graphs
Random Structures &Algorithms, Volume 66, Issue 2, March 2025.ABSTRACT Let μ(G)$$ \mu (G) $$ denote the minimum number of edges whose addition to G$$ G $$ results in a Hamiltonian graph, and let μ^(G)$$ \hat{\mu}(G) $$ denote the minimum number of edges whose addition to G$$ G $$ results in a pancyclic graph. We study the distributions of μ(G),μ^(G)$$ \mu (G),\hat{\mu}(G) $$ in the context of binomial random ...
Yahav Alon, Michael Anastos
wiley +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
Decomposition of the Product of Cycles Based on Degree Partition
Discussiones Mathematicae Graph Theory, 2019 The Cartesian product of n cycles is a 2n-regular, 2n-connected and bi- pancyclic graph. Let G be the Cartesian product of n even cycles and let 2n = n1+ n2+ ・ ・ ・ + nkwith k ≥ 2 and ni≥ 2 for each i. We prove that if k = 2, then G can be decomposed into
Borse Y. M., Shaikh S. R.
doaj +1 more source
On the Clean Graph of Commutative Artinian Rings
International Journal of Mathematics and Mathematical Sciences, Volume 2025, Issue 1, 2025.For a commutative Artinian ring R with unity, the clean graph Cl(R) is a graph with vertices in the form of an ordered pair (e, u), where e is an idempotent and u is a unit of ring R, respectively. Two distinct vertices (e, u) and (f, v) are adjacent in Cl(R) if and only if ef = fe = 0 or uv = vu = 1.
R. Singh +3 more
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
Hamiltonian and Pancyclic Graphs in the Class of Self-Centered Graphs with Radius Two
Discussiones Mathematicae Graph Theory, 2018 The paper deals with Hamiltonian and pancyclic graphs in the class of all self-centered graphs of radius 2. For both of the two considered classes of graphs we have done the following. For a given number n of vertices, we have found an upper bound of the
Hrnčiar Pavel, Monoszová Gabriela
doaj +1 more source