Cycle and path embedding on 5-ary N-cubes

Tsong-Jie Lin; Sun-Yuan Hsieh; Hui-Ling Huang

Displaying similar documents to “Cycle and path embedding on 5-ary N-cubes”

Graphs isomorphic to their path graphs

Martin Knor, Ľudovít Niepel (2002)

Mathematica Bohemica

Similarity:

We prove that for every number $n \geq 1$ , the $n$ -iterated $P_{3}$ -path graph of $G$ is isomorphic to $G$ if and only if $G$ is a collection of cycles, each of length at least 4. Hence, $G$ is isomorphic to $P_{3} (G)$ if and only if $G$ is a collection of cycles, each of length at least 4. Moreover, for $k \geq 4$ we reduce the problem of characterizing graphs $G$ such that $P_{k} (G) ≅ G$ to graphs without cycles of length exceeding $k$ .

Cycle-pancyclism in bipartite tournaments I

Hortensia Galeana-Sánchez (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let T be a hamiltonian bipartite tournament with n vertices, γ a hamiltonian directed cycle of T, and k an even number. In this paper, the following question is studied: What is the maximum intersection with γ of a directed cycle of length k? It is proved that for an even k in the range 4 ≤ k ≤ [(n+4)/2], there exists a directed cycle $C_{h (k)}$ of length h(k), h(k) ∈ k,k-2 with $| A (C_{h (k)}) \cap A (γ) | \geq h (k) - 3$ and the result is best possible. In a forthcoming paper the case of directed cycles of length k, k even and k <...

Containers and wide diameters of $P_{3} (G)$

Daniela Ferrero, Manju K. Menon, A. Vijayakumar (2012)

Mathematica Bohemica

Similarity:

The $P_{3}$ intersection graph of a graph $G$ has for vertices all the induced paths of order 3 in $G$ . Two vertices in $P_{3} (G)$ are adjacent if the corresponding paths in $G$ are not disjoint. A $w$ -container between two different vertices $u$ and $v$ in a graph $G$ is a set of $w$ internally vertex disjoint paths between $u$ and $v$ . The length of a container is the length of the longest path in it. The $w$ -wide diameter of $G$ is the minimum number $l$ such that there is a $w$ -container of length at most $l$ between any pair...

Cycle-pancyclism in bipartite tournaments II

Hortensia Galeana-Sánchez (2004)

Discussiones Mathematicae Graph Theory

Similarity:

Let T be a hamiltonian bipartite tournament with n vertices, γ a hamiltonian directed cycle of T, and k an even number. In this paper the following question is studied: What is the maximum intersection with γ of a directed cycle of length k contained in T[V(γ)]? It is proved that for an even k in the range (n+6)/2 ≤ k ≤ n-2, there exists a directed cycle $C_{h (k)}$ of length h(k), h(k) ∈ k,k-2 with $| A (C_{h (k)}) \cap A (γ) | \geq h (k) - 4$ and the result is best possible. In a previous paper a similar result for 4 ≤ k ≤ (n+4)/2 was...

Histories in path graphs

Ludovít Niepel (2007)

Discussiones Mathematicae Graph Theory

Similarity:

For a given graph G and a positive integer r the r-path graph, $P_{r} (G)$ , has for vertices the set of all paths of length r in G. Two vertices are adjacent when the intersection of the corresponding paths forms a path of length r-1, and their union forms either a cycle or a path of length k+1 in G. Let $P_{r}^{k} (G)$ be the k-iteration of r-path graph operator on a connected graph G. Let H be a subgraph of $P_{r}^{k} (G)$ . The k-history $P_{r}^{- k} (H)$ is a subgraph of G that is induced by all edges that take part in the recursive...

Paths of low weight in planar graphs

Igor Fabrici, Jochen Harant, Stanislav Jendrol' (2008)

Discussiones Mathematicae Graph Theory

Similarity:

The existence of paths of low degree sum of their vertices in planar graphs is investigated. The main results of the paper are: 1. Every 3-connected simple planar graph G that contains a k-path, a path on k vertices, also contains a k-path P such that for its weight (the sum of degrees of its vertices) in G it holds $w_{G} (P) : = \sum_{u \in V (P)} d e g_{G} (u) \leq (3 / 2) k ² + (k)$ 2. Every plane triangulation T that contains a k-path also contains a k-path P such that for its weight in T it holds $w_{T} (P) : = \sum_{u \in V (P)} d e g_{T} (u) \leq k ² + 13 k$ 3. Let G be a 3-connected simple planar graph of...

A conjecture on cycle-pancyclism in tournaments

Hortensia Galeana-Sánchez, Sergio Rajsbaum (1998)

Discussiones Mathematicae Graph Theory

Similarity:

Let T be a hamiltonian tournament with n vertices and γ a hamiltonian cycle of T. In previous works we introduced and studied the concept of cycle-pancyclism to capture the following question: What is the maximum intersection with γ of a cycle of length k? More precisely, for a cycle Cₖ of length k in T we denote $I_{γ} (C ₖ) = | A (γ) \cap A (C ₖ) |$ , the number of arcs that γ and Cₖ have in common. Let $f (k, T, γ) = m a x I_{γ} (C ₖ) | C ₖ \subset T$ and f(n,k) = minf(k,T,γ)|T is a hamiltonian tournament with n vertices, and γ a hamiltonian cycle of T. In previous...

Finding vertex-disjoint cycle cover of undirected graph using the least-squares method

Lamač, Jan, Vlasák, Miloslav

Similarity:

We investigate the properties of the least-squares solution of the system of equations with a matrix being the incidence matrix of a given undirected connected graph $G$ and we propose an algorithm that uses this solution for finding a vertex-disjoint cycle cover (2-factor) of the graph $G$ .