Browse

You are looking at 1 - 10 of 4,984 items for :

  • Mathematics x
Clear All
Open access

Marc Besson and Barry Tesman

Abstract

In this paper, we consider T-colorings of directed graphs. In particular, we consider as a T-set the set Tr = {0, 1, 2, . . ., r−1, r+1, . . .}. Exact values and bounds of the Tr-span of directed graphs whose underlying graph is a wheel graph are presented.

Open access

Bing Wang, Jian-Liang Wu and Lin Sun

Abstract

A total-k-coloring of a graph G is a coloring of VE using k colors such that no two adjacent or incident elements receive the same color. The total chromatic number χ′′(G) of G is the smallest integer k such that G has a total-k-coloring. Let G be a graph embedded in a surface of Euler characteristic ε ≥ 0. If G contains no 3-cycles adjacent to 4-cycles, that is, no 3-cycle has a common edge with a 4-cycle, then χ′′(G) ≤ max{8,Δ+1}.

Open access

Yuefang Sun, Zemin Jin and Jianhua Tu

Abstract

A total-colored graph G is rainbow total-connected if any two vertices of G are connected by a path whose edges and internal vertices have distinct colors. The rainbow total-connection number, denoted by rtc(G), of a graph G is the minimum number of colors needed to make G rainbow total-connected. In this paper, we prove that rtc(G) can be bounded by a constant 7 if the following three cases are excluded: diam() = 2, diam() = 3, contains exactly two connected components and one of them is a trivial graph. An example is given to show that this bound is best possible. We also study Erdős-Gallai type problem for the rainbow total-connection number, and compute the lower bounds and precise values for the function f(n, k), where f(n, k) is the minimum value satisfying the following property: if |E(G)| ≥ f(n, k), then rtc(G) ≤ k.

Open access

Gary Chartrand, Stephen Devereaux, Teresa W. Haynes, Stephen T. Hedetniemi and Ping Zhang

Abstract

Let G be a nontrivial connected, edge-colored graph. An edge-cut R of G is called a rainbow cut if no two edges in R are colored the same. An edge-coloring of G is a rainbow disconnection coloring if for every two distinct vertices u and v of G, there exists a rainbow cut in G, where u and v belong to different components of GR. We introduce and study the rainbow disconnection number rd(G) of G, which is defined as the minimum number of colors required of a rainbow disconnection coloring of G. It is shown that the rainbow disconnection number of a nontrivial connected graph G equals the maximum rainbow disconnection number among the blocks of G. It is also shown that for a nontrivial connected graph G of order n, rd(G) = n−1 if and only if G contains at least two vertices of degree n − 1. The rainbow disconnection numbers of all grids Pm _ Pn are determined. Furthermore, it is shown for integers k and n with 1 ≤ kn − 1 that the minimum size of a connected graph of order n having rainbow disconnection number k is n + k − 2. Other results and a conjecture are also presented.

Open access

Boštjan Brešar, Tatiana Romina Hartinger, Tim Kos and Martin Milanič

Abstract

Ho proved in [A note on the total domination number, Util. Math. 77 (2008) 97–100] that the total domination number of the Cartesian product of any two graphs without isolated vertices is at least one half of the product of their total domination numbers. We extend a result of Lu and Hou from [Total domination in the Cartesian product of a graph and K 2 or Cn, Util. Math. 83 (2010) 313–322] by characterizing the pairs of graphs G and H for which γt(GH)=12γt(G)γt(H) , whenever γt(H) = 2. In addition, we present an infinite family of graphs Gn with γt(Gn) = 2n, which asymptotically approximate equality in γt(GnHn)12γt(Gn)2.

Open access

Hengzhe Li, Baoyindureng Wu and Weihua Yang

Abstract

Let G = (V,E) be a graph and SV. We say that S is a dominating set of G, if each vertex in V \ S has a neighbor in S. Moreover, we say that S is a connected (respectively, 2-edge connected or 2-connected) dominating set of G if G[S] is connected (respectively, 2-edge connected or 2-connected). The domination (respectively, connected domination, or 2- edge connected domination, or 2-connected domination) number of G is the cardinality of a minimum dominating (respectively, connected dominating, or 2-edge connected dominating, or 2-connected dominating) set of G, and is denoted γ(G) (respectively γ1(G), or γ′ 2(G), or γ2(G)). A well-known result of Duchet and Meyniel states that γ1(G) ≤ 3γ(G) − 2 for any connected graph G. We show that if γ(G) ≥ 2, then γ′ 2(G) ≤ 5γ(G) − 4 when G is a 2-edge connected graph and γ2(G) ≤ 11γ(G) − 13 when G is a 2-connected triangle-free graph.

Open access

Samia Kerdjoudj, Alexandr Kostochka and André Raspaud

Abstract

A star edge-coloring of a graph G is a proper edge coloring such that every 2-colored connected subgraph of G is a path of length at most 3. For a graph G, let the list star chromatic index of G, ch′st(G), be the minimum k such that for any k-uniform list assignment L for the set of edges, G has a star edge-coloring from L. Dvořák, Mohar and Šámal asked whether the list star chromatic index of every subcubic graph is at most 7. We prove that it is at most 8. We also prove that if the maximum average degree of a subcubic graph G is less than 73 (respectively, 52), then ch′ st(G) ≤ 5 (respectively, ch′ st(G) ≤ 6).

Open access

Bin Wang, Longmin Wang and Kainan Xiang

Abstract

In this paper, through the coupling and martingale method, we prove the order of the largest component in some critical random intersection graphs is n23 with high probability and the width of scaling window around the critical probability is n13; while in some graphs, the order of the largest component and the width of the scaling window around the critical probability depend on the parameters in the corresponding definition of random intersection graphs. Our results show that there is still an “inside” phase transition in critical random intersection graphs.

Open access

Y.M. Borse and Ganesh Mundhe

Abstract

Slater introduced the point-addition operation on graphs to characterize 4-connected graphs. The Г-extension operation on binary matroids is a generalization of the point-addition operation. In general, under the Г-extension operation the properties like graphicness and cographicness of matroids are not preserved. In this paper, we obtain forbidden minor characterizations for binary matroids whose Г-extension matroids are graphic (respectively, cographic).

Open access

Hamideh Aram, Maryam Atapour and Seyed Mahmoud Sheikholeslami

Abstract

An eternal m-secure set of a graph G = (V,E) is a set S 0V that can defend against any sequence of single-vertex attacks by means of multiple guard shifts along the edges of G. The eternal m-security number σm(G) is the minimum cardinality of an eternal m-secure set in G. The eternal m-security bondage number b σm (G) of a graph G is the minimum cardinality of a set of edges of G whose removal from G increases the eternal m-security number of G. In this paper, we study properties of the eternal m-security bondage number. In particular, we present some upper bounds on the eternal m-security bondage number in terms of eternal m-security number and edge connectivity number, and we show that the eternal m-security bondage number of trees is at most 2 and we classify all trees attaining this bound.