• Chỉ mục bởi
  • Năm xuất bản

A maximizing characteristic for critical configurations of chip-firing games on digraphs

Nguyen H.T. Institute of Mathematics, Vietnam Academy of Science and Technology, 18 Hoang Quoc Viet street, Cau Giay district, Hanoi, Viet Nam|
Tran T.T.H. Vietnamese-German University, Le Lai street, Hoa Phu ward, Thu Dau Mot City, Binh Duong, Viet Nam|

Discrete Applied Mathematics Số , năm 2018 (Tập 250, trang 38-46)

DOI: 10.1016/j.dam.2018.05.005

Tài liệu thuộc danh mục: Scopus

Discrete Appl Math


Từ khóa: Directed graphs; Equivalence classes; Chip-firing game; Critical configurations; Duality; Optimizers; Superstable configurations; Graph theory
Tóm tắt tiếng anh
Aval et al. proved in Aval et al. (2016) that starting from a critical configuration of a chip-firing game on an undirected graph, one can never achieve a stable configuration by reverse firing any non-empty subsets of its vertices. In this paper, we generalize the result to digraphs with a global sink where reverse firing subsets of vertices is replaced with reverse firing multi-subsets of vertices. Consequently, a combinatorial proof for the duality between critical configurations and superstable configurations on digraphs is given. Finally, by introducing the concept of energy vector assigned to each configuration, we show that critical and superstable configurations are the unique ones with the greatest and smallest (w.r.t. the containment order), respectively, energy vectors in each of their equivalence classes. � 2018 Elsevier B.V.

Xem chi tiết