Embedding and the rotational dimension of a graph containing a clique. (English) Zbl 1516.05122
Summary: The rotational dimension is a minor-monotone graph invariant related to the dimension of a Euclidean space containing a spectral embedding corresponding to the first nonzero eigenvalue of the graph Laplacian, which is introduced by F. Göring et al. [J. Graph Theory 66, No. 4, 283–302 (2011; Zbl 1213.05167)]. In this paper, we study rotational dimensions of graphs which contain large complete graphs. The complete graph is characterized by its rotational dimension. It will be obtained that a chordal graph may be made large while keeping the rotational dimension constant.
MSC:
| 05C50 | Graphs and linear algebra (matrices, eigenvalues, etc.) |
| 05C62 | Graph representations (geometric and intersection representations, etc.) |
| 05C83 | Graph minors |
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
Citations:
Zbl 1213.05167References:
| [1] | Bodlaender, H. L., A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci.209(1-2) (1998) 1-45. · Zbl 0912.68148 |
| [2] | Boyd, S. and Vandenberghe, L., Convex Optimization (Cambridge University Press, Cambridge, 2004). · Zbl 1058.90049 |
| [3] | Fiedler, M., Laplacian of graphs and algebraic connectivity, Banach Center Publ.25 (1989) 57-70. · Zbl 0731.05036 |
| [4] | Göring, F., Helmberg, C. and Wappler, M., Embedded in the shadow of the separator, SIAM J. Optim.19 (2008) 472-501. · Zbl 1169.05347 |
| [5] | Göring, F., Helmberg, C. and Wappler, M., The rotational dimension of a graph, J. Graph Theory.66 (2011) 283-302. · Zbl 1213.05167 |
| [6] | Van der Holst, H., Laurent, M. and Schrijver, A., On a minor-monotone graph invariant, J. Combin. Theory Ser. B65(2) (1995) 291-304. · Zbl 0839.05034 |
| [7] | Van der Holst, H., Lovász, L. and Schrijver, A., The Colin de Verdière graph parameter, in Graph Theory and Combinatorial Biology, , Vol. 7 (János Bolyai Mathematical Society, Budapest, 1999), pp. 29-85. · Zbl 0930.05065 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
