Nothing Special   »   [go: up one dir, main page]

skip to main content
research-article

Mixed matchings in graphs

Published: 01 February 2020 Publication History

Abstract

Let n, s be integers, n ≥ 2 ( s + 1 ) ≥ 4. Let F, G ⊂ [ n ] 2 be two graphs. We determine the exact maximum of | F | + | G | subject to the condition that there is no matching of size s + 1 contained in F ∪ G and having non-empty intersection with both F and G.

References

[1]
Akiyama J., Frankl P., On the size of graphs with complete-factors, J. Graph Theory 9 (1985) 197–201.
[2]
Erdős P., A problem on independent r-tuples, Ann. Univ. Sci. Budapest 8 (1965) 93–95.
[3]
Erdős P., Gallai T., On the minimal number of vertices representing the edges of a graph, Publ. Math. Inst. Hung. Acad. Sci. 6 (1961) 181–203.
[4]
Erdős P., Ko C., Rado R., Intersection theorems for systems of finite sets, Q. J. Math. 12 (1) (1961) 313–320.
[5]
Frankl P., On the maximum number of edges in a hypergraph with given matching number, Discrete Appl. Math. 216 (2017) 562–581.
[6]
Lovász L., Combinatorial Problems and Exercises, second ed., American Mathematical Society, Providence, Rhode Island, 1993.

Index Terms

  1. Mixed matchings in graphs
        Index terms have been assigned to the content through auto-classification.

        Recommendations

        Comments

        Please enable JavaScript to view thecomments powered by Disqus.

        Information & Contributors

        Information

        Published In

        cover image Discrete Mathematics
        Discrete Mathematics  Volume 343, Issue 2
        Feb 2020
        361 pages

        Publisher

        Elsevier Science Publishers B. V.

        Netherlands

        Publication History

        Published: 01 February 2020

        Author Tags

        1. Graphs
        2. Matchings
        3. Extremal problems

        Qualifiers

        • Research-article

        Contributors

        Other Metrics

        Bibliometrics & Citations

        Bibliometrics

        Article Metrics

        • 0
          Total Citations
        • 0
          Total Downloads
        • Downloads (Last 12 months)0
        • Downloads (Last 6 weeks)0
        Reflects downloads up to 29 Nov 2024

        Other Metrics

        Citations

        View Options

        View options

        Login options

        Media

        Figures

        Other

        Tables

        Share

        Share

        Share this Publication link

        Share on social media