Title | ||
---|---|---|
On the Cartesian product of of an arbitrarily partitionable graph and a traceable graph. |
Abstract | ||
---|---|---|
A graph G of order n is called arbitrarily partitionable (AP, for short) if, for every sequence tau = (n(1), ... , n(k)) of positive integers that sum up to n, there exists a partition (V-1, ... , V-k) of the vertex set V(G) such that each set V-i induces a connected subgraph of order n(i). A graph G is called AP+1 if, given a vertex u is an element of V(G) and an index q is an element of{1, ... , k}, such a partition exists with u is an element of V-q. We consider the Cartesian product of AP graphs. We prove that if G is AP+1 and H is traceable, then the Cartesian product G square H is AP+1. We also prove that G square H is AP, whenever G and H are AP and the order of one of them is not greater than four. |
Year | Venue | Keywords |
---|---|---|
2014 | DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE | partitions of graphs,Cartesian product of graphs,traceable graphs |
Field | DocType | Volume |
Integer,Discrete mathematics,Graph,Combinatorics,Vertex (geometry),Existential quantification,Cartesian product,Vertex connectivity,Partition (number theory),Mathematics | Journal | 16.0 |
Issue | ISSN | Citations |
1.0 | 1462-7264 | 2 |
PageRank | References | Authors |
0.38 | 8 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Olivier Baudon | 1 | 60 | 10.38 |
Julien Bensmail | 2 | 69 | 18.43 |
Rafał Kalinowski | 3 | 48 | 10.75 |
Antoni Marczyk | 4 | 66 | 10.91 |
Jakub Przybyło | 5 | 210 | 27.55 |
Mariusz Wozniak | 6 | 111 | 19.51 |