2018-11-01
Dyadic representations of graphs
Publication
Publication
Discrete Mathematics , Volume 341 - Issue 11 p. 3021- 3028
A graph G is dyadic provided it has a representation v → S v from vertices v of G to subtrees S v of a host tree T with maximum degree 3 such that
(i)v and w are adjacent in G if and only if S v and S w share at least three nodes and
(ii) each edge of T is used by exactly two representing subtrees.
We show that a connected graph is dyadic if and only if it can be constructed from edges and cycles by gluing vertices to vertices and edges to edges.
Additional Metadata | |
---|---|
, , , , | |
doi.org/10.1016/j.disc.2018.07.019, hdl.handle.net/1765/109795 | |
Discrete Mathematics | |
Organisation | Department of Econometrics |
Jamison, R., & Mulder, M. (2018). Dyadic representations of graphs. Discrete Mathematics, 341(11), 3021–3028. doi:10.1016/j.disc.2018.07.019 |