Delne kocke in njihovi izpeljani grafi : doktorska disertacija = Partial cubes and their derived graphs : doctoral thesis
Kovše, Matjaž
The results of thesis concern isometric subgraphs of hypercubes-partial cubes. Four different kinds of derived graphs of partial cubes and interplay among them are considered. It is shown that ...induced cycles in crossing graphs of median graphs imply some induced cogwheel in original graphs. It is proved that for ebvery graph G there exists a median graph M such that ▫$G=M^\tau$▫, that is connected if and only if G is a Cartesian prime graph, and that for a median graph G its -graph is Kn- free if and only if G contains no convex K1,n. Graphs that are 2-connected trees, or complete graphs are characterized. Crossing graphs, -graphs and -graphs are also compared. Using the close connection between crossing graphs and semicube graphs, it is shown that, roughly speaking, every graph can be realized as the semicube graph of some partial cube. Terminal semicubes and terminal expansions are introduced along the way, generalizing ther notion of peripheral subgraphs and peripheral expansions of median graphs. Semicube graphs of trees are studied in detail. The three different types of dimension of a partial cubes are considered: the isometric, lattice and three dimension. All three dimensions are compared and partial cubes with equal isometric, lattice and tree dimension are characterized in several ways. Lattice dimension of benzenoid systems is determined using isometric embedding of benzenoid systems into the Cartesian product of three trees. The question of Fukuda and Handa whether every even partial cube G is also harmonic-even is considered. It is shown that the answer is positive if the isometric dimension of G equals its diameter which is in turn true for partial cubes with isometric dimension at most 6. Under an additional technical condition it is proved that an even partial cube G is harmonic-even or has two adjacent vertices whose diametrical vertices are at distance at least 4. It is also shown that even partial cubes are of depth 1.
Type of material - dissertation
; adult, serious
Publication and manufacture - [S. l. : M. Kovše], 2008
It was not necessary to add the material to the shelf.
Bibliographic material was successfully added on shelf.
Adding bibliographical material on shelf was not successful.
Material is already on the shelf.
Permalink
URL:
Impact factor
Access to the JCR database is permitted only to users from Slovenia. Your current IP address is not on the list of IP addresses with access permission, and authentication with the relevant AAI accout is required.
Year
Impact factor
Edition
Category
Classification
JCR
SNIP
JCR
SNIP
JCR
SNIP
JCR
SNIP
Select the library membership card:
DRS,
in which the journal is indexed
Database name
Field
Year
Links to authors' personal bibliographies
Links to information on researchers in the SICRIS system
Subject headings in COBISS General List of Subject Headings
Select pickup location
The material from the parent unit is free. If the material is delivered to the pickup location from another unit, the library may charge you for this service.
