A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with par...A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.展开更多
Let k be a positive integer. A Roman k-dominating function on a graph G is a labeling f ： V（G） → {0, 1, 2} such that every vertex with label 0 has at least k neighbors with label 2. A set {f1, f2,..., fd} of disti...Let k be a positive integer. A Roman k-dominating function on a graph G is a labeling f ： V（G） → {0, 1, 2} such that every vertex with label 0 has at least k neighbors with label 2. A set {f1, f2,..., fd} of distinct Roman k-dominating functions on G with the property that ∑di=1 fi（v） ≤ 2 for each v C V（G）, is called a Roman k-dominating family （of functions） on G. The maximum number of functions in a Roman k-dominating family on G is the Roman k-domatic number of G, denoted by dkR（G）. Note that the Roman 1-domatic number dlR（G） is the usual Roman domatic number dR（G）. In this paper we initiate the study of the Roman k-domatic number in graphs and we present sharp bounds for dkR（G）. In addition, we determine the Roman k-domatic number of some graphs. Some of our results extend those given by Sheikholeslami and Volkmann in 2010 for the Roman domatic number.展开更多
Let D be a finite and simple digraph with vertex set V(D).The minimum degreeδof a digraph D is defined as the minimum value of its out-degrees and its in-degrees.If D is a digraph with minimum degreeδand edge-connec...Let D be a finite and simple digraph with vertex set V(D).The minimum degreeδof a digraph D is defined as the minimum value of its out-degrees and its in-degrees.If D is a digraph with minimum degreeδand edge-connectivity λ,then λ≤δ.A digraph is maximally edge-connected ifλ=δ.A digraph is called super-edge-connected if every minimum edge-cut consists of edges incident to or from a vertex of minimum degree.In this note we show that a digraph is maximally edge-connected or super-edge-connected if the number of arcs is large enough.展开更多
A subset S of vertices of a graph G with no isolated vertex is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex in V （G） S is also adjacent to a vertex in V （G） S. Th...A subset S of vertices of a graph G with no isolated vertex is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex in V （G） S is also adjacent to a vertex in V （G） S. The total restrained domination number of G is the minimum cardinality of a total restrained dominating set of G. In this paper we initiate the study of total restrained bondage in graphs. The total restrained bondage number in a graph G with no isolated vertex, is the minimum cardinality of a subset of edges E such that G E has no isolated vertex and the total restrained domination number of G E is greater than the total restrained domination number of G. We obtain several properties, exact values and bounds for the total restrained bondage number of a graph.展开更多
文摘A graph G is close to regular or more precisely a （d, d ＋ k）-graph, if the degree of each vertex of G is between d and d ＋ k. Let d ≥ 2 be an integer, and let G be a connected bipartite （d, d＋k）-graph with partite sets X and Y such that ｜X｜- ｜Y｜＋1. If G is of order n without an almost perfect matching, then we show in this paper that·n ≥ 6d ＋7 when k = 1,·n ≥ 4d＋ 5 when k = 2,·n ≥ 4d＋3 when k≥3.Examples will demonstrate that the given bounds on the order of G are the best possible.
文摘Let k be a positive integer. A Roman k-dominating function on a graph G is a labeling f ： V（G） → {0, 1, 2} such that every vertex with label 0 has at least k neighbors with label 2. A set {f1, f2,..., fd} of distinct Roman k-dominating functions on G with the property that ∑di=1 fi（v） ≤ 2 for each v C V（G）, is called a Roman k-dominating family （of functions） on G. The maximum number of functions in a Roman k-dominating family on G is the Roman k-domatic number of G, denoted by dkR（G）. Note that the Roman 1-domatic number dlR（G） is the usual Roman domatic number dR（G）. In this paper we initiate the study of the Roman k-domatic number in graphs and we present sharp bounds for dkR（G）. In addition, we determine the Roman k-domatic number of some graphs. Some of our results extend those given by Sheikholeslami and Volkmann in 2010 for the Roman domatic number.
文摘Let D be a finite and simple digraph with vertex set V(D).The minimum degreeδof a digraph D is defined as the minimum value of its out-degrees and its in-degrees.If D is a digraph with minimum degreeδand edge-connectivity λ,then λ≤δ.A digraph is maximally edge-connected ifλ=δ.A digraph is called super-edge-connected if every minimum edge-cut consists of edges incident to or from a vertex of minimum degree.In this note we show that a digraph is maximally edge-connected or super-edge-connected if the number of arcs is large enough.
文摘A subset S of vertices of a graph G with no isolated vertex is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex in V （G） S is also adjacent to a vertex in V （G） S. The total restrained domination number of G is the minimum cardinality of a total restrained dominating set of G. In this paper we initiate the study of total restrained bondage in graphs. The total restrained bondage number in a graph G with no isolated vertex, is the minimum cardinality of a subset of edges E such that G E has no isolated vertex and the total restrained domination number of G E is greater than the total restrained domination number of G. We obtain several properties, exact values and bounds for the total restrained bondage number of a graph.
