✦ LIBER ✦

The -step competition graphs of doubly partial orders

✍ Scribed by Boram Park; Jung Yeun Lee; Suh-Ryung Kim

Publisher: Elsevier Science
Year: 2011
Tongue: English
Weight: 239 KB
Volume: 24
Category: Article
ISSN: 0893-9659
DOI: 10.1016/j.aml.2010.12.009

No coin nor oath required. For personal study only.

✦ Synopsis

The competition graph of a doubly partial order is an interval graph. The competitioncommon enemy graph, a variant of the competition graph, of a doubly partial order is also an interval graph if it does not contain a 4-cycle as an induced subgraph. It is natural to ask whether or not the same phenomenon occurs for other interesting variants of the competition graph. In this paper, we study the m-step competition graph, a generalization of the competition graph, of a doubly partial order. We show that the m-step competition graph of a doubly partial order is an interval graph for every positive integer m. We also show that given a positive integer m, an interval graph with sufficiently many isolated vertices is the m-step competition graph of a doubly partial order.

📜 SIMILAR VOLUMES

On linear extension majority graphs of p

On linear extension majority graphs of partial orders

✍ Peter C Fishburn 📂 Article 📅 1976 🏛 Elsevier Science 🌐 English ⚖ 279 KB

Zero-divisor graphs of partially ordered

Zero-divisor graphs of partially ordered sets

✍ Zhanjun Xue; Sanyang Liu 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 448 KB

Let (P, ≤) be a partially ordered set (poset, briefly) with a least element 0 and S ⊆ P. An element x ∈ P is a lower bound of S if s ≥ x for all s ∈ S. A simple graph G(P) is associated to each poset P with 0. The vertices of the graph are labeled by the elements of P, and two vertices x, y are conn

A partially ordered set of functionals c

A partially ordered set of functionals corresponding to graphs

✍ Alexander Sidorenko 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 776 KB

For a graph G whose vertices are vl, u2, . . . , v, and where E is the set of edges, we define a functional U,(h)= ss SC . . . frl,$EEh(Xi,Xj) > dPc(x~)dAxJ ... dp(x,), where h is a nonnegative symmetric function of two variables. We consider a binary relation + for graphs with fixed numbers of vert

The competition numbers of ternary Hammi

The competition numbers of ternary Hamming graphs

✍ Boram Park; Yoshio Sano 📂 Article 📅 2011 🏛 Elsevier Science 🌐 English ⚖ 243 KB

It is known to be a hard problem to compute the competition number k(G) of a graph G in general. Park and Sano (in press) [16] gave the exact values of the competition numbers of Hamming graphs H(n, q) if 1 ≤ n ≤ 3 or 1 ≤ q ≤ 2. In this paper, we give an explicit formula for the competition numbers

The orders of graphs with prescribed deg

The orders of graphs with prescribed degree sets

✍ Timothy A. Sipka 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 321 KB 👁 1 views

## Abstract The degree set 𝒟^G^ of a graph __G__ is the set of degrees of the vertices of __G.__ For a finite nonempty set __S__ of positive integers, all positive integers __p__ are determined for which there exists a graph __G__ of order __p__ such that 𝒟^G^ = __S__.

The dimension of the Cartesian product o

The dimension of the Cartesian product of partial orders

✍ William T Trotter Jr. 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 546 KB

If P and Q are partial orders, then the dimension of the cartesian product P x Q does not exceed the sum of the dimensions of P and Q. There are several known sufficient conditions for this bound to be attained, on the other hand, the only known lower bound for the dimension of a cartesian product i