摘要
设G是2-连通图,c(G)是图G的最长诱导圈的长度, c’(G)是图G的最 长诱导2-正则子图的长度。本文我们用图的特征值给出了c(G)和c’(G)的几个上界.
Let G be a 2-connected graph. Let us define c(G) the length of the longest induced cycle in G and c'(G) the maximal order of an induced 2-regular subgraph of G. In this paper, we present several upper bounds on c(G) and c'(G) of graphs in terms of eigenvalues.
出处
《运筹学学报》
CSCD
北大核心
2003年第4期50-56,共7页
Operations Research Transactions
基金
The research was supported by NNSF of China(19971027, 10271048)
Shanghai Priority Academic Discipline. The research was done while the author was visiting LRI.
关键词
2-正则诱导子图
特征值
诱导圈
上界
无向图
OR, eigenvalues, induced cycle, regular graph, induced 2-regular subgraph
