Let G= （V,A） be adigraph and k ≥ 1 an integer. For u,v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each ver...Let G= （V,A） be adigraph and k ≥ 1 an integer. For u,v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V ／ D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γk（G）, is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs GB（n, d） and generalized Kautz digraphs Gg（n, d） are good candidates for interconnection k networks. Denote △k ：=（∑j^k=0 d^j）^-1. F. Tian and J. Xu showed that [n△k] ≤ γk（GB（n,d）） ≤ [n/d^k] and [n△k] ≤ γk（GK（n,d）） ≤ [n/d^k]. In this paper, we prove that every generalized de Bruijn digraph GB（n, d） has the distance k- domination number [n△k] or [n△k] ＋ 1, and the distance k-domination number of every generalized Kautz digraph GK（n, d） bounded above by [n/ （d^k-1 ＋d^k）]. Additionally, we present various sufficient conditions for γk（GB（n, d）） = [n△k] and γk（GK（n, d）） = [n△k].展开更多
The ferry problem may be viewed as generalizations of the classical wolf-goatcabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conf...The ferry problem may be viewed as generalizations of the classical wolf-goatcabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five.展开更多
Let F be a graph.A hypergraph H is Berge-F if there is a bijection f:E(F)→E(H)such that e■f(e)for every e∈E(F).A hypergraph is Berge-F-free if it does not contain a subhypergraph isomorphic to a Berge-F hypergraph....Let F be a graph.A hypergraph H is Berge-F if there is a bijection f:E(F)→E(H)such that e■f(e)for every e∈E(F).A hypergraph is Berge-F-free if it does not contain a subhypergraph isomorphic to a Berge-F hypergraph.The authors denote the maximum number of hyperedges in an n-vertex r-uniform Berge-F-free hypergraph by ex_(r)(n,Berge-F).A(k,p)-fan,denoted by F_(k,p),is a graph on k(p-1)+1 vertices consisting of k cliques with p vertices that intersect in exactly one common vertex.In this paper they determine the bounds of ex_(r)(n,Berge-F)when F is a(k,p)-fan for k≥2,p≥3 and r≥3.展开更多
基金Acknowledgements This work was supported in part by the National Natural Science Foundation of China （Grant Nos. 11471210, 11571222, 11601262）.
文摘Let G= （V,A） be adigraph and k ≥ 1 an integer. For u,v ∈ V, we say that the vertex u distance k-dominate v if the distance from u to v at most k. A set D of vertices in G is a distance k-dominating set if each vertex of V ／ D is distance k-dominated by some vertex of D. The distance k-domination number of G, denoted by γk（G）, is the minimum cardinality of a distance k-dominating set of G. Generalized de Bruijn digraphs GB（n, d） and generalized Kautz digraphs Gg（n, d） are good candidates for interconnection k networks. Denote △k ：=（∑j^k=0 d^j）^-1. F. Tian and J. Xu showed that [n△k] ≤ γk（GB（n,d）） ≤ [n/d^k] and [n△k] ≤ γk（GK（n,d）） ≤ [n/d^k]. In this paper, we prove that every generalized de Bruijn digraph GB（n, d） has the distance k- domination number [n△k] or [n△k] ＋ 1, and the distance k-domination number of every generalized Kautz digraph GK（n, d） bounded above by [n/ （d^k-1 ＋d^k）]. Additionally, we present various sufficient conditions for γk（GB（n, d）） = [n△k] and γk（GK（n, d）） = [n△k].
基金supported by the National Natural Science Foundation of China(Nos.11871329,11571222)
文摘The ferry problem may be viewed as generalizations of the classical wolf-goatcabbage puzzle. The ferry cover problem is to determine the minimum required boat capacity to safely transport n items represented by a conflict graph. The Alcuin number of a conflict graph is the smallest capacity of a boat for which the graph possesses a feasible ferry schedule. In this paper the authors determine the Alcuin number of regular graphs and graphs with maximum degree at most five.
基金supported by the National Natural Science Foundation of China(Nos.11871329,11971298)。
文摘Let F be a graph.A hypergraph H is Berge-F if there is a bijection f:E(F)→E(H)such that e■f(e)for every e∈E(F).A hypergraph is Berge-F-free if it does not contain a subhypergraph isomorphic to a Berge-F hypergraph.The authors denote the maximum number of hyperedges in an n-vertex r-uniform Berge-F-free hypergraph by ex_(r)(n,Berge-F).A(k,p)-fan,denoted by F_(k,p),is a graph on k(p-1)+1 vertices consisting of k cliques with p vertices that intersect in exactly one common vertex.In this paper they determine the bounds of ex_(r)(n,Berge-F)when F is a(k,p)-fan for k≥2,p≥3 and r≥3.
