Search
Search Results
-
Path Puzzles: Discrete Tomography with a Path Constraint is Hard
We prove that path puzzles with complete row and column information—or equivalently, 2D orthogonal discrete tomography with Hamiltonicity...
-
Correction to: Bounds on Signless Laplacian Eigenvalues of Hamiltonian Graphs
In our original paper the incorrect labelling of the number of vertices of the line graph L(G) in the proof of Theorem 2 has led to the inequality
-
Equalising the Transmission Properties of Graph-Modelled Networks by Introducing the Control of the Resources Used to Transmit Information
The object of the presented paper is to demonstrate the possibility of equalizing the transmission properties of networks described by graphs with an...
-
A generalization of a theorem of Nash-Williams
Chvátal (J Combin Theory Ser B 12:163–168, 1972) gave a well-known sufficient condition for a graphical sequence to be forcibly hamiltonian, and...
-
On Subdivision Graphs Which Are 2-steps Hamiltonian Graphs and Hereditary Non 2-steps Hamiltonian Graphs
Let G be a graph with vertex set V(G) and edge set E(G). A (p, q)-graph \(G = (V,E)\)...
-
Cycles of Many Lengths in Hamiltonian Graphs
In 1999, Jacobson and Lehel conjectured that for \(k \ge 3\)...
-
-
A Generalization of the Graph Packing Theorems of Sauer-Spencer and Brandt
We prove a common generalization of the celebrated Sauer-Spencer packing theorem and a theorem of Brandt concerning finding a copy of a tree inside a...
-
Traversability in Line Graphs
In this chapter we look first at which line graphs are Eulerian and which graphs are the line graphs of Eulerian graphs, both of which have nice...
-
-
Tight Bounds for Powers of Hamilton Cycles in Tournaments
A basic result in graph theory says that any n-vertex tournament with in- and out-degrees larger than...
-
Best Monotone Degree Condition for the Hamiltonicity of Graphs with a 2-Factor
We give a sufficient degree condition for the hamiltonicity of graphs with a 2-factor which is best possible in the same sense that Chvátal’s...
-
Cycle Spectra of Contraction-Critically 4-Connected Planar Graphs
Motivated by the long-standing and wide open pancyclicity conjectures of Bondy and Malkevitch, we study the cycle spectra of contraction-critically...
-
Hamiltonicity, minimum degree and leaf number
We prove a new sufficient condition for a connected graph to be Hamiltonian in terms of the leaf number and the minimum degree. Our results give...
-
Domination and its variants in split graphs -P versus NPC dichotomy
We investigate the complexity of minimum total outer-connected domination in split graphs. Given a connected graph G , a minimum total outer-connected...
-
Resolving The Hamiltonian Problem for Vertex-Transitive Graphs of Order a Product of Two Primes
A step forward is made in a long standing Lovász problem regarding existence of Hamilton paths in vertex-transitive graphs. It is shown that a...
-
-
On the Extraconnectivity of Arrangement Graphs
Extraconnectivity generalizes the concept of connectivity of a graph but it is more difficult to compute. In this note, we compute the...
-
Euclidean Bottleneck Bounded-Degree Spanning Tree Ratios
Inspired by the seminal works of Khuller et al. (SIAM J. Comput. 25 (2), 355–368 (1996)) and Chan (Discrete Comput. Geom. 32 (2), 177–194 (2004)) we...
