johnson graphs

On the generalized $\varthetahBcnumber and related problems for highly symmetric graphs

  • Lennart Sinjorgo
  • Renata Sotirov
    • Categories Graphs and Matroids, Linear, Cone and Semidefinite Programming Tags , , , , ,

    This paper is an in-depth analysis of the generalized $\vartheta$-number of a graph. The generalized $\vartheta$-number, $\vartheta_k(G)$, serves as a bound for both the $k$-multichromatic number of a graph and the maximum $k$-colorable subgraph problem. We present various properties of $\vartheta_k(G)$, such as that the series $(\vartheta_k(G))_k$ is increasing and bounded above by the order … Read more

    On bounding the bandwidth of graphs with symmetry

  • Renata Sotirov
  • Edwin van Dam
    • Categories Semi-definite Programming Tags , , , , ,

    We derive a new lower bound for the bandwidth of a graph that is based on a new lower bound for the minimum cut problem. Our new semide finite programming relaxation of the minimum cut problem is obtained by strengthening the well-known semide nite programming relaxation for the quadratic assignment problem by fixing two vertices in the … Read more