Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Dense Arbitrarily Partitionable Graphs

Rafał Kalinowski;  Monika Pilśniak;  Ingo Schiermeyer;  Mariusz Woźniak — 2016

Discussiones Mathematicae Graph Theory

A graph G of order n is called arbitrarily partitionable (AP for short) if, for every sequence (n1, . . . , nk) of positive integers with n1 + ⋯ + nk = n, there exists a partition (V1, . . . , Vk) of the vertex set V (G) such that Vi induces a connected subgraph of order ni for i = 1, . . . , k. In this paper we show that every connected graph G of order n ≥ 22 and with [...] ‖G‖ > (n−42)+12 | | G | | > n - 4 2 + 12 edges is AP or belongs to few classes of exceptional graphs.

Distinguishing Cartesian Products of Countable Graphs

Ehsan Estaji;  Wilfried Imrich;  Rafał Kalinowski;  Monika Pilśniak;  Thomas Tucker — 2017

Discussiones Mathematicae Graph Theory

The distinguishing number D(G) of a graph G is the minimum number of colors needed to color the vertices of G such that the coloring is preserved only by the trivial automorphism. In this paper we improve results about the distinguishing number of Cartesian products of finite and infinite graphs by removing restrictions to prime or relatively prime factors.

Page 1

Download Results (CSV)