Student: Ilia Izmailov

College: Princeton University

    Department: Mathematics

    Graduation Year: 2007 (rising senior)

REU E-mail: izmailov@dimax.rutgers.edu

School E-mail: izmailov@math.princeton.edu

Faculty Advisor: Prof. Vadim Lozin, RUTCOR

Research Area: Graph Theory

Project Number: DIMACS2006-03

Project Description

Terminology:

    Vertex: A point. One of the two possible components of a graph. Distinguished from edge.

    Edge: A line connecting two vertices. One of the two possible components of a graph. Distinguished from vertex.

    Adjacent: (of two vertices) Connected by an edge. Two adjacent vertices are called neighbors.

    Degree (of a vertex): The number of edges emanating from it.

    Induced Subgraph: Graph formed by the removal of all vertices not belonging to a fixed subset, along with the edges incident to them..

    Clique: Subset of a graph's vertices that induce a connected graph.

    Clique separator: Clique that induces a subgraph C such that its removal from the main graph disconnects it..

    Connected graph: Graph where any two vertices are connected by a path, representable via a subset of the edges.

    2-connected graph: Graph that cannot be made disconnected via a removal of any vertex along with the edges incident from it.

                Figure 1. Example of a connected graph that is not 2-connected: a removal of the middle vertex disconnects it.

    Clique-separator free: Having no clique separators. NOTE: a 2-connected graph is free of all trivial, i.e. single point, clique separators.

    Claw: An induced subgraph consisting of a vertex of degree 3, known as the center, each of whose neighbors has degree 1.

                  Figure 2. Typical claw. The blue vertex is its center.

    Cycle of order k (C_k): An induced subgraph consisting of k vertices, each of degree 2.

            Figure 3. An example of a cycle C₉.

    Apple of order k (A_k): An induced subgraph consisting of a cycle of order k, one of whose vertices has a degree of 3 and is adjacent to a degree 1 vertex.

            Figure 4. An example of a apple A₅.

    Module: A subset U of a graph's vertices such that each vertex outside of U contains both a neighbor and a non-neighbor within the module.

    Prime Graph: Graph in which every module is trivial, i.e. has a unit cardinality.

    Independent Set: Set of vertices, no two of which are adjacent.

Background:

The problem of finding a maximal independent of vertices on a particular graph is NP-hard. However, it can be shown that a graph that is either claw-free or (C_kC_k+1C_k+2...)-free, the problem can be solved in polynomial time. As Lozin and Milanič [1] have shown, a prime graph that is free of large apples (whose order exceeds a predefined constant), clique separators, and vertices of degree greater than d = 3 is either claw-free or cycle-free, hence another one of these special cases that can be solved with relative speed.

Problem:

What, if anything, is special, about the constant d being equal to 3? Can d not be any fixed constant.

Approach:

The only practicable way of solving this problem is by contradiction: one must being by assuming an apple-free graph has both a claw and a large cycle and making the argument fail. For that, it is necessary to consider a large number of cases (as compare to just 2 in the case of d = 3) which can take a long time to analyze by hand. A good solution would be to conduct a computer simulation.

Sources

   [1] Lozin, Vadim and Martin Milanič. "Maximum Independent Sets in Graphs of Low Degree." (unpublished)

Last Updated: Friday, June 30, 2006 11:19:12 PM