Some Covering and Packing Problems for Mixed Triples

A mixed graph has both edges and directed edges (or “arcs”). A complete mixed graph on v vertices, denoted Mv, has, for every pair of vertices u and v, an edge {u,v}, an arc (u,v), and an arc (v,u). A decomposition of the complete mixed graph on v vertices into a partial orientation of a three-cycle...

Full description

Saved in:
Bibliographic Details
Published in:AppliedMath 2024-12, Vol.4 (4), p.1245-1255
Main Authors: Bobga, Benkam, Gardner, Robert
Format: Article
Language:English
Subjects:
graph covering
graph decomposition
graph packing
mixed graph
mixed triples
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A mixed graph has both edges and directed edges (or “arcs”). A complete mixed graph on v vertices, denoted Mv, has, for every pair of vertices u and v, an edge {u,v}, an arc (u,v), and an arc (v,u). A decomposition of the complete mixed graph on v vertices into a partial orientation of a three-cycle with one edge and two arcs (of which there are three types) is a mixed triple system of order v. Necessary and sufficient conditions for the existence of a mixed triple system of order v are well known. In this work packings and coverings of the complete mixed graph with mixed triples are considered. Necessary conditions are given for each of the three relevant mixed triples, and these conditions are shown to be sufficient for two of the relevant mixed triples. For the third mixed triple, a conjecture is given concerning the sufficient conditions. Applications of triple systems in general are discussed, as well as possible applications of mixed graphs, mixed triple systems, and packings and coverings with mixed triples.
ISSN:2673-9909
2673-9909
DOI:10.3390/appliedmath4040067