# Search results for: Irene Heinrich

Journal of Graph Theory > 94 > 2 > 224 - 251

Graphs and Combinatorics > 2018 > 34 > 6 > 1203-1216

Discrete Mathematics > 2018 > 341 > 1 > 119-125

Journal of Graph Theory > 94 > 2 > 224 - 251

Hajós' conjecture asserts that a simple Eulerian graph on $n$ vertices can be decomposed into at most $\lfloor \left(n-1\right)/2\rfloor $ cycles. The conjecture is only proved for graph classes in which every element contains vertices of degree 2 or 4. We develop new techniques to construct cycle decompositions. They work on the common neighborhood of two degree‐6 vertices. With these techniques, we find structures...

Graphs and Combinatorics > 2018 > 34 > 6 > 1203-1216

The neighborhood complex of a graph is the family of subsets of open neighborhoods of its vertices. The neighborhood polynomial is the ordinary generating function for the number of sets of the neighborhood complex with respect to their cardinality. This paper provides a new representation of the neighborhood polynomial as a sum over complete bipartite subgraphs of a graph. Using the close relation...

Discrete Mathematics > 2018 > 341 > 1 > 119-125

A prominent parameter in the context of network analysis, originally proposed by Watts and Strogatz (1998), is the clustering coefficient of a graph G . It is defined as the arithmetic mean of the clustering coefficients of its vertices, where the clustering coefficient of a vertex u of G is the relative density m ( G [ N G ( u ) ] ) ∕ d G ( u ) 2 of its neighborhood...