the forwarding indices of graphs - a survey

the forwarding indices of graphs - a survey

;Jun-Ming Xu;Min Xu
zhonghua yi xue za zhi 2013 Vol. 33 pp. 345-372
179
xu2013opusculathe

Abstract

A routing \(R\) of a connected graph \(G\) of order \(n\) is a collection of \(n(n-1)\) simple paths connecting every ordered pair of vertices of \(G\). The vertex-forwarding index \(\xi(G,R)\) of \(G\) with respect to a routing \(R\) is defined as the maximum number of paths in \(R\) passing through any vertex of \(G\). The vertex-forwarding index \(\xi(G)\) of \(G\) is defined as the minimum \(\xi(G,R)\) over all routings \(R\) of \(G\). Similarly, the edge-forwarding index \(\pi(G,R)\) of \(G\) with respect to a routing \(R\) is the maximum number of paths in \(R\) passing through any edge of \(G\). The edge-forwarding index \(\pi(G)\) of \(G\) is the minimum \(\pi(G,R)\) over all routings \(R\) of \(G\). The vertex-forwarding index or the edge-forwarding index corresponds to the maximum load of the graph. Therefore, it is important to find routings minimizing these indices and thus has received much research attention for over twenty years. This paper surveys some known results on these forwarding indices, further research problems and several conjectures, also states some difficulty and relations to other topics in graph theory.

Citation

ID: 194032
Ref Key: xu2013opusculathe
Use this key to autocite in SciMatic or Thesis Manager

References

Blockchain Verification

Account:
NFT Contract Address:
0x95644003c57E6F55A65596E3D9Eac6813e3566dA
Article ID:
194032
Unique Identifier:
http://dx.doi.org/10.7494/OpMath.2013.33.2.345
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