Characterizing the Existence of P4

Authors

  • Pinaki Mitra Department of CSE, IIT Guwahati, Guwahati, India

DOI:

https://doi.org/10.37591/rrdms.v1i3.223

Keywords:

P4, Complement graph, star Sub-graph, induction

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.

Author Biography

  • Pinaki Mitra, Department of CSE, IIT Guwahati, Guwahati, India

    RESUME
    Name : Pinaki Mitra
    Date of birth : 1st January, 1966
    Address: Department of Computer Sc. & Engg.
    IIT Guwahati
    North Guwahati
    Guwahati – 781039.
    Phone # (011-91-361) 258-4352 (Res)
    (011-91-361) 258-2352 (Office)
    Mobile: 9957195620
    Email : [email protected]
    Areas of Interest :
    i) Cryptography & Security.
    ii) Optimization.
    iii) Computational Geometry.
    iv) Parallel Algorithms.
    v) Randomized Algorithms.
    Qualifications :
    i) Madhyamik Examination, Hindu School, 1981, (746/900), 82.89%, 1st division.
    ii) Higher Secondary Examination, St. Xavier's College, 1983, (846/1000), 84.6%, 1st
    division.
    iii) B.E, Computer Science, Jadavpur University, Calcutta, 1987, 86.14%, 1st class with
    honours.
    iv) M.E, Computer Science, Indian Institute of Science, Bangalore, 1989, 6.7/8.0, 1st
    class.
    v) Ph.D, Computer Science, Simon Fraser University, Canada, 1994, 3.56/4.0.
    Present Occupation :
    Associate Professor, Department of Computer Science and Engineering, Indian Institute
    of Technology, Guwahati. (October 2008 onwards)
    Current Annual Salary: Rs. 7,56, 000/- (Approx.)
    Work Experience :
    i) Taught Database Systems, Grande Prairie Regional College, Alberta, Canada.
    (Sept. 1994 -- Feb. 1995).
    ii) Post-doctoral Fellow, MRCO Research Group, Carleton University, Canada.
    (March 1995 -- May 1995).
    iii) Research Scientist, Project on Storage Retrieval and Understanding of Video for
    Multimedia, Computer Science and Engineering Department, Jadavpur
    University.(April 1996 -- May 1999).
    iv) Research Scientist, Center for Microprocessor Training Education and Research,
    Computer Science and Engineering Department, Jadavpur University.(May 1999 -
    - June 2000).
    v) Assistant Professor, National Institute of Management Calcutta (July 2000 –
    December 2004).
    vi) Assistant Professor, Indian Institute of Technology Guwahati (December 2004 –
    October 2008).
    Taught :
    a) Systems Programming in Department of Computer Science, Jadavpur University,
    Calcutta.
    b) Numerical analysis and C programming in Production Engineering Department,
    Jadavpur University, Calcutta.
    c) Compiler Design, Theory of Computer Science, Graph Theory in IEM Salt Lake,
    Calcutta.
    d) Computer Organization & Architecture in Electronics & Telecommunication
    Enggineering Department, Jadavpur University, Calcutta.
    e) Java Programming in SRUVM Project, Jadavpur University, Calcutta.
    f) Data Structures, Design and Analysis of Algorithms, Introduction to Digital
    Electronics, Database Systems, Cryptography and Data Security at National
    Institute of Management Calcutta (NIMC).
    g) Java Programming at MBM Department, Calcutta University.
    h) Algorithms, Optimization, Data Structures, Computational Number Theory &
    Cryptography, Theory of Computation & Computer Graphics at IIT Guwahati,
    Publications :
    Refereed Indian Journals:
    i) P. Mitra, "A Comparative Analysis of Huffman Coding", The IUP Journal of
    Computer Sciences, Vol VI, No. 1, January 2012, pp. 17 -- 22.
    ii) P. Mitra, S. Swain, Zero Knowledge Interactive Proof for Elliptic Curve Discrete
    Logarithm Problem (ECDLP), International J. of Advanced Computing (IJAC),
    vol. 1, 2010.
    iii) P. Mitra, C. S. Chowdary, Novel Method for Improving the Exact Matching of the
    Molecular Graphs, International Journal of Recent Trends in Engineering, 2009.
    iv) P. Mitra, M. Durgaprasada Rao and M. Kranthi Kumar, Algorithms to Compute a
    Generator of the Group (Zp
    *, ×p) and Safe Primes, International Journal of
    Information Processing.
    v) P. Mitra M. Nasipuri & D. K. Basu, Improved Image Data Compression for
    Multimedia Applications, International Journal of Information & Computing
    Science.
    Refereed Foreign Journals:
    i) P. Mitra, G. Sundaram and A. Tripathi, Business Process Based Database
    Recovery and Experimental Results, Int. J. of Database Management Systems
    (IJDMS), Vol. 3, No. 4, November 2011, pp. 118 – 130.
    ii) P. Mitra, G. Sundaram, S. G. Kumar and V. Kurup, Mail Plugin for IBM
    Mashup Center, International Journal of Electronic Commerce Studies, Vol.
    1, No.2, 2010, pp. 139 –148.
    iii) P.Mitra and K. Baid, Generation of Targeted Advertising for Online Social
    Networks, International Journal of Web Applications, pp. 129 -- 136 .
    iv) P. Mitra & B. B. Chaudhuri, Efficiently Computing the Closest Point to a
    Query Line, Pattern Recognition Letters 19 (1998), pp. 1027 -- 1035.
    v) P. Mitra & S. C. Nandy, Efficient Computation of Rectilinear Geodesic
    Voronoi Neighbor in Presence of Obstacles, J. of Algorithms, 28(2) : 315,
    1998 August.
    vi) P. Mitra, Answering Gabriel Neighbour Queries, Pattern Recognition Letters,
    13(1992), pp. 557 -- 560.
    vii) H. ElGindy & P.Mitra, Orthogonal Shortest Route Queries Among Axes
    Parallel Rectangular Obstacles, Int. J. of Comput. Geom. & Appl., 4(1), 1994,
    pp. 3 -- 24.
    Un-refereed Journals:
    i) P. Mitra & L. Hafer, Efficient Computation of the Medial Axes, Technical
    Report # CMPT TR 98-07, Simon Fraser University.
    International Conference Papers:
    i) Ashish Kumar, Sachin Kumar, Dr. Pinaki Mitra, Girish Sundaram, System
    and Methods for Converting Speech to SQL, Proceedings of International
    Conference on Emerging Research in Computing, Information,
    Communication and Applications, ERCICA-13.
    ii) P. Mitra, G. Sundaram, S. G. Kumar and V. Kurup, Mail Plugin for IBM
    Mashup Center, International Conference on Internet Studies, Taipei, Paiwan.
    iii) P Mitra and M. Samal, Approximation Algorithm For Correlation Clustering,
    NDT 2009.
    iv) P Mitra and K. Baid, Targeted Advertising for Online Social Networks, NDT
    2009.
    v) P. Mitra and N. Amarnadh, Upper Bound on Dilation of Triangulations of
    Cyclic Polygons, ICCSA 2006, Glasgow, U.K, LNCS 3980, pp. 1 -- 10.
    vi) P. Mitra and C. Chaudhuri, Efficient Algorithm for the Extraction of
    Association Rules in Data Mining, ICCSA 2006, Glasgow, U.K, LNCS 3981,
    pp. 1 -- 10.
    viii) P. Mitra, A. Mukhopadhyay and S.V. Rao, Efficiently Computing the closest
    point to a query ring, manuscript (accepted in CCCG 2003, Halifax, Nova
    Scotia).
    ix) P. Mitra and A. Mukhopadhyay, Computing the Closest Point to a Query
    Hyperplane in Higher Dimensions, LNCS 2669, Part III, ICCSA 2003,
    Montreal, May 2003, pp. 787 -- 796.
    x) P. Mitra & B.K. Bhattacharya, Efficient Approximate Shortest Path Query
    Among Isothetic Rectangular Obstacles, WADS'93, pp. 518 -- 529.
    xi) P. Mitra, Efficient Parallel Shortest Path Algorithms for K-Chordal Graphs,
    International Parallel Processing Symposium 1992, pp. 88 – 94.
    National Conference Papers:
    i) P. Mitra and S. Swain, Supersingularity and Cyclicity of Elliptic Curves,
    National Workshop on Network Security (NWNS) 2010, Tezpur University.
    ii) K. Narendra, S. V. Rao, P. Mitra and P. Viswanath, Speeding up of Polynomial
    Time Isomorphic Matching of Molecular Graphs, International Conference on
    Data Management, ICDM 2010, Gazhiabad, India.
    iii) P. Mitra & S. C. Nandy, Efficient Computation of Rectilinear Geodesic
    Voronoi Neighbor in Presence of Obstacles, FST&TCS, Lecture Notes in
    Computer Science 1180, Springer Verlag, 1996, pp. 76 --87.
    iv) P. Mitra M. Nasipuri & D. K. Basu, Improved Image Data Compression for
    Multimedia Applications, International Seminar on International Business
    Through Internet (IBTI-99), pp. 31 -- 41.
    v) P. Mitra and Nanigopal Das, Distributed Join Algorithm on Expander
    Networks, ReTIS 2006, pp. 9 – 12.
    Fellowship :
    Awarded S.F.U President's Ph.D Research Stipend.
    Other Activities :
    i) Referred papers for Algorithmica, Information Processing Letters, Pattern
    Recognition Letters, IISC Journal, Robotics and Computer Integrated
    Manufacturing.
    ii) Reviewed papers for A.C.M Symposium on Computational Geometry, ReTIS –
    2006, CIT- 2006, ICIT-2007.
    iii) Organized a QIP STC “Application Specific Algorithms: Design & Analysis”
    in IIT(G) during July 4 – 8, 2006.
    iv) Organized a QIP STC “Data Structures & Algorithms” in IIT(G) during July 4
    – 8, 2011.
    -----------------------------------------------

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.

Downloads

Published

2014-12-23

Issue

Vol. 1 No. 3 (2014)

Section

Research Articles

License

Declaration and Copyright Transfer Form

(to be completed by authors)

I/ We, the undersigned author(s) of the submitted manuscript, hereby declare, that the above manuscript which is submitted for publication in the STM Journals(s), is not published already in part or whole (except in the form of abstract) in any journal or magazine for private or public circulation, and, is not under consideration of publication elsewhere.

  • I/We will not withdraw the manuscript after 1 week of submission as I have read the Author Guidelines and will adhere to the guidelines.
  • I/We Author(s ) have niether given nor will give this manuscript elsewhere for publishing after submitting in STM Journal(s).
  • I/ We have read the original version of the manuscript and am/ are responsible for the thought contents embodied in it. The work dealt in the manuscript is my/ our own, and my/ our individual contribution to this work is significant enough to qualify for authorship.
  •  I/We also agree to the authorship of the article in the following order:

Author’s name                                    

 

1. ________________

2. ________________

3. ________________

4. ________________

 

We  Author(s) tick this box and would request you to consider it as our signature as we agree to the terms of this Copyright Notice, which will apply to this submission if and when it is published by this journal.