Page 1 Next

## Displaying 1 – 20 of 234

Showing per page

### 2-factors in claw-free graphs with locally disconnected vertices

Czechoslovak Mathematical Journal

An edge of $G$ is singular if it does not lie on any triangle of $G$; otherwise, it is non-singular. A vertex $u$ of a graph $G$ is called locally connected if the induced subgraph $G\left[N\left(u\right)\right]$ by its neighborhood is connected; otherwise, it is called locally disconnected. In this paper, we prove that if a connected claw-free graph $G$ of order at least three satisfies the following two conditions: (i) for each locally disconnected vertex $v$ of degree at least $3$ in $G,$ there is a nonnegative integer $s$ such that $v$ lies...

### '3in1' enhanced: three squared ways to '3in1' GRAPHS

Discussiones Mathematicae Graph Theory

### A conjecture on the prevalence of cubic bridge graphs

Discussiones Mathematicae Graph Theory

Almost all d-regular graphs are Hamiltonian, for d ≥ 3 . In this note we conjecture that in a similar, yet somewhat different, sense almost all cubic non-Hamiltonian graphs are bridge graphs, and present supporting empirical results for this prevalence of the latter among all connected cubic non-Hamiltonian graphs.

### A Fan-Type Heavy Pair Of Subgraphs For Pancyclicity Of 2-Connected Graphs

Discussiones Mathematicae Graph Theory

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), dK(u, v) = 2 implies [...] min⁡dG(u),dG(v)≥n+12 $min\left\{{d}_{G}\left(u\right),{d}_{G}\left(v\right)\right\}\ge \frac{n+1}{2}$ . In this paper we prove that every 2-connected K1,3, P5-f1-heavy graph is pancyclic. This result completes the answer to the problem of finding f1-heavy pairs of subgraphs implying pancyclicity...

### A Hamiltonian cycle and a $1$-factor in the fourth power of a graph

Časopis pro pěstování matematiky

### A Hamiltonian property of connected sets in the alternative set theory.

Acta Mathematica Universitatis Comenianae. New Series

### A Lower Bound for the Optimal Crossing-Free Hamiltonian Cycle Problem.

Discrete &amp; computational geometry

### A matching and a Hamiltonian cycle of the fourth power of a connected graph

Mathematica Bohemica

The following result is proved: Let $G$ be a connected graph of order $geq4$. Then for every matching $M$ in ${G}^{4}$ there exists a hamiltonian cycle $C$ of ${G}^{4}$ such that $E\left(C\right)\bigcap M=0$.

### A New Necessary Condition for the Vertex Visibility Graphs of Simple Polygons.

Discrete &amp; computational geometry

### A New Proof that 4-Connected Planar Graphs are Hamiltonian-Connected

Discussiones Mathematicae Graph Theory

We prove a theorem guaranteeing special paths of faces in 2-connected plane graphs. As a corollary, we obtain a new proof of Thomassen’s theorem that every 4-connected planar graph is Hamiltonian-connected.

### A note on a new condition implying pancyclism

Discussiones Mathematicae Graph Theory

We first show that if a 2-connected graph G of order n is such that for each two vertices u and v such that δ = d(u) and d(v) < n/2 the edge uv belongs to E(G), then G is hamiltonian. Next, by using this result, we prove that a graph G satysfying the above condition is either pancyclic or isomorphic to ${K}_{n/2,n/2}$.

### A Note on Barnette’s Conjecture

Discussiones Mathematicae Graph Theory

Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian. We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.

### A note on Hamiltonian cycles in generalized Halin graphs

Discussiones Mathematicae Graph Theory

We show that every 2-connected (2)-Halin graph is Hamiltonian.

### A note on maximal common subgraphs of the Dirac's family of graphs

Discussiones Mathematicae Graph Theory

Let ⁿ be a given set of unlabeled simple graphs of order n. A maximal common subgraph of the graphs of the set ⁿ is a common subgraph F of order n of each member of ⁿ, that is not properly contained in any larger common subgraph of each member of ⁿ. By well-known Dirac’s Theorem, the Dirac’s family ⁿ of the graphs of order n and minimum degree δ ≥ [n/2] has a maximal common subgraph containing Cₙ. In this note we study the problem of determining all maximal common subgraphs of the Dirac’s family...

### A note on optimality conditions for dual problems to the traveling salesman problem

Applicationes Mathematicae

### A note on the number of edges guaranteeing a ${C}_{4}$ in Eulerian bipartite digraphs.

The Electronic Journal of Combinatorics [electronic only]

### A note on the number of Hamiltonian paths in strong tournaments.

The Electronic Journal of Combinatorics [electronic only]

### A note on the Song-Zhang theorem for Hamiltonian graphs

Colloquium Mathematicae

An independent set S of a graph G is said to be essential if S has a pair of vertices that are distance two apart in G. In 1994, Song and Zhang proved that if for each independent set S of cardinality k+1, one of the following condition holds: (i) there exist u ≠ v ∈ S such that d(u) + d(v) ≥ n or |N(u) ∩ N(v)| ≥ α (G); (ii) for any distinct u and v in S, |N(u) ∪ N(v)| ≥ n - max{d(x): x ∈ S}, then G is Hamiltonian. We prove that if for each essential...

### A Note on the Total Detection Numbers of Cycles

Discussiones Mathematicae Graph Theory

Let G be a connected graph of size at least 2 and c :E(G)→{0, 1, . . . , k− 1} an edge coloring (or labeling) of G using k labels, where adjacent edges may be assigned the same label. For each vertex v of G, the color code of v with respect to c is the k-vector code(v) = (a0, a1, . . . , ak−1), where ai is the number of edges incident with v that are labeled i for 0 ≤ i ≤ k − 1. The labeling c is called a detectable labeling if distinct vertices in G have distinct color codes. The value val(c) of...

### A note on the total number of double Eulerian circuits in multigraphs.

Journal of Integer Sequences [electronic only]

Page 1 Next