Cardinality of relations with applications

Rudolf Berghammer; Nikita Danilenko; Peter Höfner; Insa Stucke

doi:10.1016/j.disc.2016.06.019

Cardinality of relations with applications

Rudolf Berghammer^*, Nikita Danilenko, Peter Höfner, Insa Stucke

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

3 Citations (Scopus)

Abstract

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.

Original language	English
Pages (from-to)	3089-3115
Number of pages	27
Journal	Discrete Mathematics
Volume	339
Issue number	12
DOIs	https://doi.org/10.1016/j.disc.2016.06.019
Publication status	Published - 6 Dec 2016
Externally published	Yes

Access to Document

10.1016/j.disc.2016.06.019

Cite this

@article{77151d8390dd4d17ba07f70f05971a51,

title = "Cardinality of relations with applications",

abstract = "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{\H o}nig that in bipartite graphs the matching number equals the vertex cover number.",

keywords = "Bipartite relation, Cardinality operation, Decomposition, Graph parameter, Matching, Point axiom, Relation algebra, Vertex cover",

author = "Rudolf Berghammer and Nikita Danilenko and Peter H{\"o}fner and Insa Stucke",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier B.V.",

year = "2016",

month = dec,

day = "6",

doi = "10.1016/j.disc.2016.06.019",

language = "English",

volume = "339",

pages = "3089--3115",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "12",

}

TY - JOUR

T1 - Cardinality of relations with applications

AU - Berghammer, Rudolf

AU - Danilenko, Nikita

AU - Höfner, Peter

AU - Stucke, Insa

PY - 2016/12/6

Y1 - 2016/12/6

N2 - 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.

AB - 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.

KW - Bipartite relation

KW - Cardinality operation

KW - Decomposition

KW - Graph parameter

KW - Matching

KW - Point axiom

KW - Relation algebra

KW - Vertex cover

UR - http://www.scopus.com/inward/record.url?scp=84979517443&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2016.06.019

DO - 10.1016/j.disc.2016.06.019

M3 - Article

SN - 0012-365X

VL - 339

SP - 3089

EP - 3115

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 12

ER -

Cardinality of relations with applications

Abstract

Access to Document

Other files and links

Fingerprint

Cite this