Trustworthy Systems

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

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