有向图的双超连通性

作者：李静静, 刘娟

单位：李静静, 女, 硕士研究生,研究方向为图论与组合数学. E-mail: 804474119@qq.com.

摘要：简单有向图(无环与重弧),如果满足每个最小点割都是某个点的出邻点集或入邻点集,则称是超连通的. 在超连通有向图中,如果存在一个最小点割既是某个点的出邻点集又是某个点的入邻点集,则称是双超连通的. 主要研究了线图双超连通性的充要条件; 同时,研究了笛卡尔积与字典积的双超连通性.

关键词：组合问题,超连通,双超连通性,线图,笛卡尔积,

基金资助：基金项目: 国家自然科学基金~(61363020, 11301450);新疆维吾尔自治区青年科技创新人才培养工程(2013731011);新疆维吾尔自治区自然科学基金\,(2012211B21); 新疆研究生科技创新项目(2014118)