• 検索結果がありません。

Boˇstjan Breˇsar, Sandi Klavˇzar  F=HJE= ?K>AI =@ CH=FDI MEJD ?LAN EJAHL=I

N/A
N/A
Info
ダウンロード
Protected

Academic year: 2022

シェア "Boˇstjan Breˇsar, Sandi Klavˇzar  F=HJE= ?K>AI =@ CH=FDI MEJD ?LAN EJAHL=I"

Copied!
1
0
0

読み込み中.... (全文を見る)

今ダウンロードする ( 1 ページ )

全文

(1)

Boˇstjan Breˇsar, Sandi Klavˇ zar

On partial cubes and graphs with convex intervals

Comment.Math.Univ.Carolinae 43,3 (2002) 537-545.

Abstract: A graph is called a partial cube if it admits an isometric embedding into a hypercube. Subdivisions of wheels are considered with respect to such embeddings and with respect to the convexity of their intervals. This allows us to answer in negative a question of Chepoi and Tardif from 1994 whether all bipartite graphs with convex intervals are partial cubes. On a positive side we prove that a graph which is bipartite, has convex intervals, and is not a partial cube, always contains a subdivision ofK4.

Keywords: isometric embeddings, hypercubes, partial cubes, convex intervals, subdivisions

AMS Subject Classification: 05C12, 05C75

1

参照

今ダウンロードする ( PDF - 1 ページ - 44.86 KB )

関連したドキュメント

Solutions that are positive with respect to a cone are obtained for the boundary value problem,u(n)+a(t)f(u

Henderson, Singular nonlinear boundary value problems for higher order ordinary differential equations, Nonlin.. Henderson, Focal points and comparison theorems for a class of two

We propose also a new approach which enables us to prove a unique solvability of the nonlocal problem with integral condition

S.; On the Solvability of Boundary Value Problems with a Nonlocal Boundary Condition of Integral Form for Multidimentional Hyperbolic Equations, Differential Equations, 2006, vol..

In this paper, we give a complete answer to Problem 1 and a partial answer to Problem 2 posed by F

SHI, Solution of an open problem proposed by Feng Qi, RGMIA Research Report Collection, 10(4)

ON OPEN PROBLEMS OF F. QI

Abstract: In this paper, we give a complete answer to Problem 1 and a partial answer to Problem 2 posed by F.. Qi in [2] and we propose an

On partial cubes and graphs with convex intervals

Isometric subgraphs of hypercubes (called partial cubes), which are pre- cisely bipartite partial Hamming graphs, have been first investigated in the sev- enties by Graham and

We prove that almost all i-iterated line graphs are selfcentric with radius i+ 2

The following lemma enables us to compute distances between nodes in iterated line graphs:.. Lemma

We introduce the concept of (k, l)-radius of a graph and prove that for any fixed pairk, lthe (k, l)-radius is equal to 2 k2 − l 2 for almost all graphs

The transmission of the graph, also called a distance of the graph, is defined as the sum of distances between all pairs of vertices (for general properties of the distance see

It is also proved that every graph is isomorphic to an induced subgraph of a Merris graph and conjectured that almost all graphs are not Merris graphs

Some families of Merris graphs are found, including Kneser graphs K ( v, 2) and non-singular regular bipar- tite graphs.. For example, the Petersen graph and the Clebsch graph turn