Projects / Programmes
Structural and algebraic properties of graph classes
| Code |
Science |
Field |
Subfield |
| 1.01.05 |
Natural sciences and mathematics |
Mathematics |
Graph theory |
| Code |
Science |
Field |
| P110 |
Natural sciences and mathematics |
Mathematical logic, set theory, combinatories |
graph, distance, convexity, discrete metric space, gatedness, Cartesian product, direct product, median, quasi-median graph, chordal graph, imprint, partial cube, isometric subgraph, retract, automorphism
Researchers (1)
| no. |
Code |
Name and surname |
Research area |
Role |
Period |
No. of publicationsNo. of publications |
| 1. |
17005 |
PhD Boštjan Brešar |
Mathematics |
Head |
2002 - 2004 |
403 |
Organisations (1)
Abstract
In this project we shall investigate structural and algebraic properties of some important graph classes. We are concerned with graphs defined either by metric properties, by certain elimination procedures, or as subgraphs of product graphs. Main attention of research will be given to properties derived from the distance in graphs such as convexity, gatednes and interval, and new characterizations of graph classes shall be obtained using forbidden subgraphs, certain equivalence relations defined on graphs, and other structural properties. The main focus will be given to median graphs and their generalizations, notably quasi-median graphs and partial cubes. We shall study the relations on these graphs that connect the number of induced hypercubes with certain graph invariants on these classes. Structural properties of these classes shall be studied, in particular we are interested in the expansion procedure. Using the expansion one can define new classes of graphs, and we will connect these classes with the existing theory. We shall investigate classes of partial cubes that can be recognized faster than median graphs. Classes of partial cubes that include median graphs and whose regular subclass consists precisely of hypercubes will be considered. For these and related classes of graphs we shall consider the existence of a hypercube that is invariant under every automorphism of graphs. We shall consider generalized median graphs as imprint function closed isometric subgraphs of Cartesian product graphs. Some relevant metric properties of this class shall be studied using known methods and concepts developed in the studies of median graphs. The existence of a special subgraph that is invariant under every automorphism of graphs, defined by a sort of amalgamation procedure will be considered, which would generalize many known results. We shall study new connections between chordal graphs, partial cubes and related classes of graphs in relation with intersection graphs of maximal hypercubes. The structure of graphs that cannot be represented as nontrivial subgraphs of Cartesian product of graphs shall be given attention, as well as some classes of graphs that can be represented as direct products of two graphs.
