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...

On the distributions of $R_{m n}^{+} (j)$ and $(D_{m n}^{+}, R_{m n}^{+} (j))$

Jagdish Saran, Kanwar Sen (1982)

Aplikace matematiky

Similarity:

The contents of the paper is concerned with the two-sample problem where $F_{m} (x)$ and $G_{n} (x)$ are two empirical distribution functions. The difference $F_{m} (x) - G_{n} (x)$ changes only at an $x_{i}, i = 1, 2, ..., m + n$ , corresponding to one of the observations. Let $R_{m n}^{+} (j)$ denote the subscript $i$ for which $F_{m} (x_{i}) - G_{n} (x_{i})$ achieves its maximum value $D_{m n}^{+}$ for the $j$ th time $(j = 1, 2, ...)$ . The paper deals with the probabilities for $R_{m n}^{+} (j)$ and for the vector $(D_{m n}^{+}, R_{m n}^{+} (j))$ under $H_{0} : F = G$ , thus generalizing the results of Steck-Simmons (1973). These results have been derived by applying the random walk model. ...

Pairs of forbidden class of subgraphs concerning $K_{1, 3}$ and P₆ to have a cycle containing specified vertices

Takeshi Sugiyama, Masao Tsugaki (2009)

Discussiones Mathematicae Graph Theory

Similarity:

In [3], Faudree and Gould showed that if a 2-connected graph contains no $K_{1, 3}$ and P₆ as an induced subgraph, then the graph is hamiltonian. In this paper, we consider the extension of this result to cycles passing through specified vertices. We define the families of graphs which are extension of the forbidden pair $K_{1, 3}$ and P₆, and prove that the forbidden families implies the existence of cycles passing through specified vertices.