Skip to main content


Cardinality of relations with applications


Rudolf Berghammer, Nikita Danilenko, Peter Hoefner and Insa Stucke

Christian-Albrechts-Universität zu Kiel




Based on Y. Kawahara’s characterisation of the cardinality of relations we derive some fundamental properties of cardinalities concerning vectors, points and mapping-related relations. As applications of these results we verify some properties of linear orders and graphs in a calculational manner. These include the cardinalities of rooted trees and some estimates concerning graph parameters. We also calculationally prove the result of D. König that in bipartite graphs the matching number equals the vertex cover number.

BibTeX Entry

    doi              = {10.1016/j.disc.2016.06.019},
    journal          = {Discrete Mathematics},
    author           = {Berghammer, Rudolf and Danilenko, Nikita and Höfner, Peter and Stucke, Insa},
    number           = {12},
    month            = dec,
    volume           = {339},
    year             = {2016},
    title            = {Cardinality of Relations with Applications},
    pages            = {3089-3115}


Served by Apache on Linux on seL4.
Served by Apache on Linux on seL4.