6533b835fe1ef96bd12a0178
RESEARCH PRODUCT
Some properties of vertex-oblique graphs
Kamila KowalskaZsolt TuzaJerzy MichaelEwa Drgas-burchardtsubject
Discrete mathematicsClique-sumNeighbourhood (graph theory)020206 networking & telecommunications0102 computer and information sciences02 engineering and technology01 natural sciencesTheoretical Computer ScienceMetric dimensionCombinatoricsIndifference graphNew digraph reconstruction conjecture010201 computation theory & mathematicsChordal graphIndependent set0202 electrical engineering electronic engineering information engineeringDiscrete Mathematics and CombinatoricsBound graphirregular graphsindependence numbervertex-oblique graphslexicographic productMathematicsdescription
The type t G ( v ) of a vertex v ? V ( G ) is the ordered degree-sequence ( d 1 , ? , d d G ( v ) ) of the vertices adjacent with v , where d 1 ? ? ? d d G ( v ) . A graph G is called vertex-oblique if it contains no two vertices of the same type. In this paper we show that for reals a , b the class of vertex-oblique graphs G for which | E ( G ) | ? a | V ( G ) | + b holds is finite when a ? 1 and infinite when a ? 2 . Apart from one missing interval, it solves the following problem posed by Schreyer et?al. (2007): How many graphs of bounded average degree are vertex-oblique? Furthermore we obtain the tight upper bound on the independence and clique numbers of vertex-oblique graphs as a function of the number of vertices. In addition we prove that the lexicographic product of two graphs is vertex-oblique if and only if both of its factors are vertex-oblique.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2016-01-01 | Discrete Mathematics |