The linear guessing number of undirected graphs

被引：2
|
作者：
Chang, Gerard Jennhwa [1 ,2 ,3 ]
Feng, Keqin [4 ]
Huang, Liang-Hao [5 ]
Lu, Mei [4 ]
机构：
[1] Natl Taiwan Univ, Dept Math, Taipei 10617, Taiwan
[2] Natl Taiwan Univ, Taida Inst Math Sci, Taipei 10617, Taiwan
[3] Natl Ctr Theoret Sci, Taipei Off, Hsinchu, Taiwan
[4] Tsinghua Univ, Dept Math Sci, Beijing 100084, Peoples R China
[5] Acad Sinica, Res Ctr Informat Technol Innovat, Taipei 115, Taiwan
来源：
LINEAR ALGEBRA AND ITS APPLICATIONS | 2014年 / 449卷
基金：
中国国家自然科学基金;
关键词：
Linear guessing number; Undirected graph; Network coding;
D O I：
10.1016/j.laa.2014.02.010
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
This paper investigates linear guessing number introduced by Riis in connection with the network coding theory. This paper establishes properties of linear guessing number on undirected graphs. In particular, lower and upper bounds for linear guessing number are established. Finally, linear guessing numbers of product graphs are investigated. (C) 2014 Elsevier Inc. All rights reserved.
引用
收藏
页码：119 / 131
页数：13
相关论文
共 44 条
  • [21] Incremental Algorithm for Maintaining a DFS Tree for Undirected Graphs
    Surender Baswana
    Shahbaz Khan
    Algorithmica, 2017, 79 : 466 - 483
  • [22] Undirected Graphs: Is the Shift-Enabled Condition Trivial or Necessary?
    Chen, Liyan
    Cheng, Samuel
    He, Kanghang
    Stankovic, Vladimir
    Stankovic, Lina
    IEEE ACCESS, 2021, 9 : 75082 - 75089
  • [23] Deterministic Õ(nm) Time Edge-Splitting in Undirected Graphs
    Hiroshi Nagamochi
    Toshihide Ibaraki
    Journal of Combinatorial Optimization, 1997, 1 : 5 - 46
  • [24] On synchronization of the double sphere Kuramoto model with connected undirected graphs
    Shi, Yushi
    Li, Ting
    Zhu, Jiandong
    PHYSICA D-NONLINEAR PHENOMENA, 2023, 443
  • [25] Multi-Session Function Computation and Multicasting in Undirected Graphs
    Kannan, Sreeram
    Viswanath, Pramod
    IEEE JOURNAL ON SELECTED AREAS IN COMMUNICATIONS, 2013, 31 (04) : 702 - 713
  • [26] Minimum augmentation of edge-connectivity with monotone requirements in undirected graphs
    Ishii, Toshimasa
    DISCRETE OPTIMIZATION, 2009, 6 (01) : 23 - 36
  • [27] ALGORITHMS FOR ENUMERATING ALL SPANNING-TREES OF UNDIRECTED AND WEIGHTED GRAPHS
    KAPOOR, S
    RAMESH, H
    SIAM JOURNAL ON COMPUTING, 1995, 24 (02) : 247 - 265
  • [28] From undirected graphs to directed graphs: a new technique makes it possible for multi-agent systems
    Zhang, Jilie
    Feng, Tao
    JOURNAL OF CONTROL AND DECISION, 2022, 9 (03) : 286 - 288
  • [29] On categoricity questions for universal unars and undirected graphs under semantic Jonsson quasivariety
    Yeshkeyev, A. R.
    Yarullina, A. R.
    Amanbekov, S. M.
    BULLETIN OF THE KARAGANDA UNIVERSITY-MATHEMATICS, 2023, 111 (03): : 165 - 180
  • [30] Minimum Augmentation of Edge-Connectivity between Vertices and Sets of Vertices in Undirected Graphs
    Ishii, Toshimasa
    Akiyama, Yoko
    Nagamochi, Hiroshi
    ALGORITHMICA, 2010, 56 (04) : 413 - 436
12345