Borse, Y.M. Mundhe, Ganesh
Published in
Discussiones Mathematicae Graph Theory

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...

Kerdjoudj, Samia Kostochka, Alexandr Raspaud, André
Published in
Discussiones Mathematicae Graph Theory

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 ...

Czap, Július Jendroľ, Stanislav Valiska, Juraj
Published in
Discussiones Mathematicae Graph Theory

An edge-colored graph G is conflict-free connected if any two of its vertices are connected by a path, which contains a color used on exactly one of its edges. In this paper the question for the smallest number of colors needed for a coloring of edges of G in order to make it conflict-free connected is investigated. We show that the answer is easy ...

Besson, Marc Tesman, Barry
Published in
Discussiones Mathematicae Graph Theory

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.

Ding, Zongpeng Huang, Yuanqiu
Published in
Discussiones Mathematicae Graph Theory

There are only few results concerning crossing numbers of join of some graphs. In this paper, for some graphs on five vertices, we give the crossing numbers of its join with n isolated vertices.

Chartrand, Gary Devereaux, Stephen Haynes, Teresa W. Hedetniemi, Stephen T. Zhang, Ping
Published in
Discussiones Mathematicae Graph Theory

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 G − R. We introduce and...

Sun, Yuefang Jin, Zemin Tu, Jianhua
Published in
Discussiones Mathematicae Graph Theory

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 ...

Aram, Hamideh Atapour, Maryam Sheikholeslami, Seyed Mahmoud
Published in
Discussiones Mathematicae Graph Theory

An eternal m-secure set of a graph G = (V,E) is a set S0 ⊆ V 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 c...

Li, Hengzhe Wu, Baoyindureng Yang, Weihua
Published in
Discussiones Mathematicae Graph Theory

Let G = (V,E) be a graph and S ⊆ V. 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, ...

Wang, Bing Wu, Jian-Liang Sun, Lin
Published in
Discussiones Mathematicae Graph Theory

A total-k-coloring of a graph G is a coloring of V ∪ E 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 ...