Covering numbers of regular multigraphs

DOI10.1007/BF01158148MaRDI QIDQ753843zbMATH OpenFDO

Authors V. E. Tarakanov

Publication date 1989

Published in Mathematical Notes (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/BF01158148

zbMATH Keywords

edge coverregular multigraph

Mathematics Subject Classification ID

Combinatorial aspects of packing and covering (05B40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (05C99)

Review text

Let n be odd. For every n-regular multigraph G on N vertices \(\alpha_ 1(G)\leq \lfloor (2n-3)N/(3n-4)\rfloor\), where \(\alpha_ 1(G)\) is the minimum size of an edge cover (i.e. a family of edges such that every vertex is incident with some of them). On the other hand, if N is a multiple of \(3n+1\) then there exists a multigraph G with \(\alpha_ 1(G)=2nN/(3n+1)\).

Recommendations

• 1-factor covers of regular graphs
• Publication:4729831
• Multicovering hypergraphs
• On the edge-independence number and edge-covering number for regular graphs
• A note on the edge cover chromatic index of multigraphs

Cites work

• An Algorithm for a Minimum Cover of a Graph
• Width Sequences for Special Classes of (0, 1)-Matrices

Cited in

(2)

• Counting some finite-fold coverings of a graph
• Counting double covers of graphs

This page was built for publication: Covering numbers of regular multigraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q753843)