Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size
From MaRDI portal
Publication:2581629
The authors provide two new sufficient conditions on a degree sequence that can correspond to a graph containing a clique of order \(r+1\): a graphic sequence \(d_1\geq\cdots\geq d_n\) is a degree sequence of a graph with clique of order \(r+1\) if \(n\geq r+1\), \(d_i\geq 2r_i\) for \(i\leq r-1\) and \(d_{r+1}\geq r\), or if \(n\geq 2r+2\), \(d_{r+1}\geq r\) and \(d_{2r-2}\geq r-1\). The established sufficient conditions are used to reprove several previous results in the area.
Recommendations
Cites work
- A note on potentially K₄-e graphical sequences
- Algorithms for constructing graphs and digraphs with given valences and factors
- An extremal problem on the potentially \(P_k\)-graphic sequences
- scientific article; zbMATH DE number 3169205 (Why is no real title available?)
- scientific article; zbMATH DE number 3758373 (Why is no real title available?)
- scientific article; zbMATH DE number 1286471 (Why is no real title available?)
- scientific article; zbMATH DE number 867707 (Why is no real title available?)
- scientific article; zbMATH DE number 2192177 (Why is no real title available?)
- The Erdős-Jacobson-Lehel conjecture on potentially \(P_k\)-graphic sequence is true
Cited in
(33)- A variation of a conjecture due to Erdös and Sós
- Exact solution to an extremal problem on graphic sequences with a realization containing every 2-tree on \(k\) vertices
- Graphic sequences with a realization containing cycles \(C_3, \dots, C_\ell \)
- A new lower bound on the potential-Ramsey number of two graphs
- Combinatorial properties of degree sequences of 3-uniform hypergraphs arising from Saind arrays
- Recognition of split-graphic sequences
- On the potential function of an arbitrary graph \(H\)
- An extremal problem on graphic sequences with a realization containing every \(\ell \)-tree on \(k\) vertices
- A sharp refinement of a result of Zverovich-Zverovich
- The smallest degree sum that yields potentially \(K_{r+1}-K_3\)-graphic sequences
- A characterization for a sequence to be potentially \({K_{r+1}-e}\)-graphic
- Graphic sequences with a realization containing intersecting cliques
- On potentially \((K_5-H)\)-graphic sequences.
- Potentially K m — G-graphical sequences: A survey
- An Erdős-Stone Type Conjecture for Graphic Sequences
- On potentially H-graphic sequences
- New results on degree sequences of uniform hypergraphs
- Stability of the potential function
- Chromatic number and complete graph substructures for degree sequences
- A note on packing of graphic \(n\)-tuples
- A note on the potential function of an arbitrary graph H
- The potential-Ramsey number of $K_n$ and $K_t^{-k}$
- Graphic sequences and split graphs
- On the sum necessary to ensure that a degree sequence is potentially H-graphic
- Solution to a general version of a degree sequence variant of the Erdős-Sós conjecture
- A characterization for a graphic sequence to be potentially \(C_{r}\)-graphic
- Closeness centrality reconstruction of tree graphs
- On the existence of tripartite graphs and n-partite graphs
- A degree sequence variant of graph Ramsey numbers
- New sufficient conditions on the degree sequences of uniform hypergraphs
- Graphic sequences with a realization containing a union of cliques
- Graphic sequences with a realization containing a generalized friendship graph
- Graphic sequences with a realization containing a complete multipartite subgraph
This page was built for publication: Two sufficient conditions for a graphic sequence to have a realization with prescribed clique size
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2581629)
