Пансвязь
В теории графов пансвязный граф — это неориентированный граф , в котором для каждых двух вершин s и t существуют пути от s до t любой возможной длины от расстояния d ( s , t ) до n − 1 , где n — количество вершин в графе. Концепция пансвязности была введена в 1975 году Юсефом Алави и Джеймсом Э. Уильямсоном. [1]
Пансвязные графы обязательно панцикличны : если uv — ребро , то оно принадлежит циклу любой возможной длины, и, следовательно, граф содержит цикл любой возможной длины.Пансвязные графы, а также являются обобщением гамильтонова связных графов (графов, у которых есть гамильтонов путь, соединяющий каждую пару вершин).
Известно, что несколько классов графов являются пансвязными:
- Если G имеет гамильтонов цикл , то квадрат G (граф на том же множестве вершин, который имеет ребро между любыми двумя вершинами, расстояние которых в G не превышает двух) является пансвязным. [1]
- Если G — любой связный граф , то куб G (граф на том же множестве вершин, у которого есть ребро между любыми двумя вершинами, расстояние которых в G не превышает трех) является пансвязным. [1]
- Если каждая вершина в n- вершинном графе имеет степень не ниже n /2 + 1 , то граф является пансвязным. [2]
- Если n -вершинный граф имеет хотя бы ( n - 1)( n - 2)/2 + 3 ребра, то граф является пансвязным. [2]
Ссылки
[ редактировать ]- ^ Jump up to: а б с Алави, Юсеф; Уильямсон, Джеймс Э. (1975), «Всесвязные графы», Венгерские исследования математических наук , 10 (1–2): 19–22, MR 0450125 .
- ^ Jump up to: а б Уильямсон, Джеймс Э. (1977), «Всесвязные графы. II», Periodica Mathematica Hungarica. Журнал Математического общества Яноша Бойяи , 8 (2): 105–116, doi : 10.1007/BF02018497 , MR 0463037 , S2CID 120309280 .