S.M. Lee proposed the conjecture: for any n > 1 and any permutation f in S(n), the permutation graph P(Pₙ,f) is graceful. For any integer n > 1 and permutation f in S(n), we discuss the gracefulness of the permutation graph P(Pₙ,f) if $f = ∏_{k = 0}^{l-1} (m+2k, m+2k+1)$, and $∏_{k=0}^{l-1} (m+4k,m+4k+2)(m+4k+1,m+4k+3)$ for any positive integers m and l.
In this paper we consider the following problem. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two edge-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂, respectively. We give a linear (O(|V|+|E|)) algorithm to solve this problem on a permutation graph.
The 'two paths problem' is stated as follows. Given an undirected graph G = (V,E) and vertices s₁,t₁;s₂,t₂, the problem is to determine whether or not G admits two vertex-disjoint paths P₁ and P₂ connecting s₁ with t₁ and s₂ with t₂ respectively. In this paper we give a linear (O(|V|+ |E|)) algorithm to solve the above problem on a permutation graph.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.