p_{m}-saturated graphs with minimum size

;Aneta Dudek;A. Paweł Wojda
zhonghua yi xue za zhi 2004 Vol. 24 pp. 43-55
156
dudek2004opusculap_{m}-saturated

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\).

Citation

ID: 246533
Ref Key: dudek2004opusculap_{m}-saturated
Use this key to autocite in SciMatic or Thesis Manager

References

Blockchain Verification

Account:
NFT Contract Address:
0x95644003c57E6F55A65596E3D9Eac6813e3566dA
Article ID:
246533
Unique Identifier:
Network:
Scimatic Chain (ID: 481)
Loading...
Blockchain Readiness Checklist
Authors
Abstract
Journal Name
Year
Title
5/5
Creates 1,000,000 NFT tokens for this article
Token Features:
  • ERC-1155 Standard NFT
  • 1 Million Supply per Article
  • Transferable via MetaMask
  • Permanent Blockchain Record
Blockchain QR Code
Scan with Saymatik Web3.0 Wallet

Saymatik Web3.0 Wallet