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

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

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

Brešar, Boštjan Hartinger, Tatiana Romina Kos, Tim Milanič, Martin
Published in
Discussiones Mathematicae Graph Theory

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

Wang, Bin Wang, Longmin Xiang, Kainan
Published in
Discussiones Mathematicae Graph Theory

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 $n^{{2 \over 3}}$ with high probability and the width of scaling window around the critical probability is n−13 $n^{ - {1 \over 3}}$ ; while in some graphs, the order of the largest component and ...

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

Koch, Arnd
Published in
Zeitschrift für die gesamte Strafrechtswissenschaft