p_{m}-saturated graphs with minimum size

Clicks: 176
ID: 246533
2004
Free PDF
Article Quality & Performance Metrics
Overall Quality
Not rated
Combines reader engagement with the AI quality analysis. This article has not been analysed, so there is no overall score — reader engagement is measured and shown alongside.
AI Quality Assessment
Not analyzed
Readership in this journal
Popular

Ranked #48 of 95 articles by views in zhonghua yi xue za zhi

Most read Least read

Bar heights use a square-root scale.

Mint this article as an NFT
Not yet minted

Create a permanent, verifiable on-chain record of this article on the Scimatic Network. The NFT is held in your Journament account, and you can withdraw it to your own wallet at any time.

5 SUSD one-off · no wallet required
Sign in to mint
Abstract
By \(P_m\) we denote a path of order \(m\). A graph \(G\) is said to be \(P_m\)-saturated if \(G\) has no subgraph isomorphic to \(P_m\) and adding any new edge to \(G\) creates a \(P_m\) in \(G\). In 1986 L. Kászonyi and Zs. Tuza considered the following problem: for given \(m\) and \(n\) find the minimum size \(sat(n;P_m)\) of \(P_m\)-saturated graph and characterize the graphs of \(Sat(n;P_m)\) - the set of \(P_m\)-saturated graphs of minimum size. They have solved this problem for \(n\geq a_m\) where \(a_m=\begin{cases}3\cdot 2^{k-1}-2 &\quad\text{ if }\quad m=2k,\, k\gt 2\\ 2^{k+1}-2 &\quad\text{ if }\quad m=2k+1,\, k\geq 2\end{cases}\). We define \(b_m=\begin{cases}3\cdot 2^{k-2} &\quad\text{ if }\quad m=2k,\, k\geq 3\\ 3\cdot 2^{k-1}-1 &\quad\text{ if }\quad m=2k+1,\, k\geq 3\end{cases}\) and give \(sat(n;P_m)\) and \(Sat(n;P_m)\) for \(m\geq 6\) and \(b_m\leq n\leq a_m\).
Reference Key
dudek2004opusculap_{m}-saturated Use this key to autocite in the manuscript while using SciMatic Manuscript Manager or Thesis Manager
Authors ;Aneta Dudek;A. Paweł Wojda
Journal zhonghua yi xue za zhi
Year 2004
DOI
DOI not found
URL
http://www.opuscula.agh.edu.pl/vol24/1/art/opuscula_math_2404.pdf
Keywords
graph quantitative methods extremal graphapplied mathematics

Citations

No citations found. To add a citation, contact the admin at info@scimatic.org

Comments

No comments yet. Be the first to comment on this article.