Factorizing the complete graph into factors with large star number

Paul Erdos; Norbert Sauer; Jonathan Schaer; Joel Spencer

doi:10.1016/0095-8956(75)90046-5

Factorizing the complete graph into factors with large star number

Paul Erdos, Norbert Sauer, Jonathan Schaer, Joel Spencer

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

Abstract

The graph G has star number n if any n vertices of G belong to a subgraph which is a star. Let f(n, k) be the smallest number m such that the complete graph on m vertices can be factorized into k factors with star number n. In the present paper we prove that c₁ⁿk ≤ f(n, k) < c₂ⁿk.

Original language	English (US)
Pages (from-to)	180-183
Number of pages	4
Journal	Journal of Combinatorial Theory, Series B
Volume	18
Issue number	2
DOIs	https://doi.org/10.1016/0095-8956(75)90046-5
State	Published - Apr 1975

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0095-8956(75)90046-5

Cite this

@article{98058f586d894fc89f37bf6d3770d555,

title = "Factorizing the complete graph into factors with large star number",

abstract = "The graph G has star number n if any n vertices of G belong to a subgraph which is a star. Let f(n, k) be the smallest number m such that the complete graph on m vertices can be factorized into k factors with star number n. In the present paper we prove that c1nk ≤ f(n, k) < c2nk.",

author = "Paul Erdos and Norbert Sauer and Jonathan Schaer and Joel Spencer",

year = "1975",

month = apr,

doi = "10.1016/0095-8956(75)90046-5",

language = "English (US)",

volume = "18",

pages = "180--183",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Factorizing the complete graph into factors with large star number

AU - Erdos, Paul

AU - Sauer, Norbert

AU - Schaer, Jonathan

AU - Spencer, Joel

PY - 1975/4

Y1 - 1975/4

N2 - The graph G has star number n if any n vertices of G belong to a subgraph which is a star. Let f(n, k) be the smallest number m such that the complete graph on m vertices can be factorized into k factors with star number n. In the present paper we prove that c1nk ≤ f(n, k) < c2nk.

AB - The graph G has star number n if any n vertices of G belong to a subgraph which is a star. Let f(n, k) be the smallest number m such that the complete graph on m vertices can be factorized into k factors with star number n. In the present paper we prove that c1nk ≤ f(n, k) < c2nk.

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

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

U2 - 10.1016/0095-8956(75)90046-5

DO - 10.1016/0095-8956(75)90046-5

M3 - Article

AN - SCOPUS:49549137768

SN - 0095-8956

VL - 18

SP - 180

EP - 183

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 2

ER -

Factorizing the complete graph into factors with large star number

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this