Open Access Open Access  Restricted Access Subscription Access

Characterizing the Existence of P4

Pinaki Mitra

Abstract


In a graph G = (V, E) P4 denotes a path of length 4 vertices <v1, v2, v3, v4> such that there is no edge between either <v1, v3> or <v2, v4>. This exists either in graph G = (V, E) or its complement or both for which both G and the complement Gc are connected. In this article we give a proof for this property.

Keywords


P4, Complement graph, star Sub-graph, induction

Full Text:

PDF

References


Corneil D.G., Lerchs H., Burlingham L.

Stewart. Complement reducible graphs,

Discrete Applied Mathematics 1981;

(3):163–174p.

Corneil D. G., Perl Y., Stewart L. K., A

linear recognition algorithm for cographs,

SIAM Journal on Computing 1985; 14(4):

(1985) 926–934.

Jamison B., Olariu S., P4-reducible graphs,

a class of uniquely tree representable

graphs. Studies in Applied Mathematics

; 81: 79–87p.

Jamison B., Olariu S., A tree

representation for P4-sparse graphs.

Discrete Applied Mathematics 1992;

(2): 115–129p.

Jamison B., Olariu S., Recognizing P4-sparse graphs in linear time, SIAM Journal on Computing 1992; 21(2):381–406p.

Jamison B., Olariu S., Linear time optimization algorithms for P4-sparse graphs Discrete Applied Mathematics 1995; 61(2): 155–175p.


Refbacks

  • There are currently no refbacks.


This site has been shifted to https://stmcomputers.stmjournals.com/