If is a permutation of , the graph has vertices where xy is an edge of if and only if (x, y) or (y, x) is an inversion of . Any graph isomorphic to is called a permutation graph. In 1967 Gallai characterized permutati...If is a permutation of , the graph has vertices where xy is an edge of if and only if (x, y) or (y, x) is an inversion of . Any graph isomorphic to is called a permutation graph. In 1967 Gallai characterized permutation graphs in terms of forbidden induced subgraphs. In 1971 Pnueli, Lempel, and Even showed that a graph is a permutation graph if and only if both the graph and its complement have transitive orientations. In 2010 Limouzy characterized permutation graphs in terms of forbidden Seidel minors. In this paper, we characterize permutation graphs in terms of a cohesive order of its vertices. We show that only the caterpillars are permutation graphs among the trees. A simple method of constructing permutation graphs is also presented here.展开更多
Abstract. Let D （U, V, W） be an oriented 3-partite graph with ｜ U ｜ = p, ｜V｜ = q and ｜W ｜ = r. For any vertex x in D（U,V,W）, let dx^＋ and dui^- be the outdegree and indegree ofx respectively. Define aui （o...Abstract. Let D （U, V, W） be an oriented 3-partite graph with ｜ U ｜ = p, ｜V｜ = q and ｜W ｜ = r. For any vertex x in D（U,V,W）, let dx^＋ and dui^- be the outdegree and indegree ofx respectively. Define aui （or simply ai） = q ＋ r ＋ dui^＋ - dui^-, bvj （or simply b j） = p ＋ r ＋ d^＋vj - d^-vj and cwk （or simply ck） =p ＋ q ＋ dwk^＋ -dwk^- as the scores of ui in U,vj in V and wk in W respectively. The set A of distinct scores of the vertices of D（U, V, W） is called its score set. In this paper, we prove that if a1 is a non-negative integer, ai（2 ≤ i ≤ n - 1） are even positive integers and an is any positive integer, then for n 〉 3, there exists an oriented 3-partite graph with the score set A ={a1,Σ2i=1 ai,…,Σni=1 ai}, except when A = {0, 2, 3}. Some more results for score sets in oriented 3-partite graphs are obtained.展开更多
文摘If is a permutation of , the graph has vertices where xy is an edge of if and only if (x, y) or (y, x) is an inversion of . Any graph isomorphic to is called a permutation graph. In 1967 Gallai characterized permutation graphs in terms of forbidden induced subgraphs. In 1971 Pnueli, Lempel, and Even showed that a graph is a permutation graph if and only if both the graph and its complement have transitive orientations. In 2010 Limouzy characterized permutation graphs in terms of forbidden Seidel minors. In this paper, we characterize permutation graphs in terms of a cohesive order of its vertices. We show that only the caterpillars are permutation graphs among the trees. A simple method of constructing permutation graphs is also presented here.
文摘Abstract. Let D （U, V, W） be an oriented 3-partite graph with ｜ U ｜ = p, ｜V｜ = q and ｜W ｜ = r. For any vertex x in D（U,V,W）, let dx^＋ and dui^- be the outdegree and indegree ofx respectively. Define aui （or simply ai） = q ＋ r ＋ dui^＋ - dui^-, bvj （or simply b j） = p ＋ r ＋ d^＋vj - d^-vj and cwk （or simply ck） =p ＋ q ＋ dwk^＋ -dwk^- as the scores of ui in U,vj in V and wk in W respectively. The set A of distinct scores of the vertices of D（U, V, W） is called its score set. In this paper, we prove that if a1 is a non-negative integer, ai（2 ≤ i ≤ n - 1） are even positive integers and an is any positive integer, then for n 〉 3, there exists an oriented 3-partite graph with the score set A ={a1,Σ2i=1 ai,…,Σni=1 ai}, except when A = {0, 2, 3}. Some more results for score sets in oriented 3-partite graphs are obtained.
