Article ID Journal Published Year Pages File Type
4949615 Discrete Applied Mathematics 2017 7 Pages PDF
Abstract
We prove that if G is a connected graph such with the independence number at most ⌈n2⌉ and the degree sum of any pair of non-adjacent vertices is at least n−3, then G is on-line arbitrarily partitionable except for two graphs of small orders. We also prove that if G is a connected graph of order n and size ‖G‖>n−32+6, then G is on-line AP unless n is even and G is a spanning subgraph of a unique exceptional graph. These two results imply that dense AP graphs satisfying one of the above two assumptions are also on-line AP. This is in contrast to sparse graphs where only few AP graphs are also on-line AP.
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
,