共查询到20条相似文献,搜索用时 93 毫秒
1.
四类粘接图的niche数 总被引:2,自引:0,他引:2
唐廷载 《高校应用数学学报(A辑)》1998,13(4):479-484
粘接图G1(u)⊙G2(υ)是将图G1的顶点u与图G2的顶点υ重合而得到的一个图.本文证明Pm(u)⊙Kn(u是Pm的起点或终点,n≥2),Km⊙Kn(m,n≥2),Pm(u)⊙Cn(n≥3)和Km⊙Cn(m≥2,n≥3)这四类图都是niche图. 相似文献
2.
有向圈的行列式算法及HAMILTON图条件 总被引:6,自引:1,他引:5
本文引入有向路乘法、弧行列式等概念 ,讨论了弧行列式的性质 ,阐述了二种计算有向圈的行列式方法及有向图 D为 Hamilton图的充要条件 ,最后给出了计算实例 相似文献
3.
4.
卜月华 《数学的实践与认识》2009,39(4)
唯一泛圈有向图D是一个定向图,对每一个n,3≤n≤υ,D中有且只有一个长为n的有向圈.用g(υ)表示具有υ个顶点的唯一泛圈有向图最小可能的弧数,用N(υ)表示具有υ个顶点、g(υ)条弧且互不同构的唯一泛圈有向图的个数.确定了当υ=3,4,5,6,7,8时的N(υ). 相似文献
5.
6.
设DKv表示完全有向对称图,C(v,m)表示覆盖DKv的m长有向圈的最小圈数(称为覆盖数).对任意正整数m和v,当m≤v≤m+6时,覆盖数C(v,m) 被确定. 相似文献
7.
8.
9.
一个有向多重图D的跳图$J(D)$是一个顶点集为$D$的弧集,其中$(a,b)$是$J(D)$的一条弧当且仅当存在有向多重图$D$中的顶点$u_1$, $v_1$, $u_2$, $v_2$,使得$a=(u_1,v_1)$, $b=(u_2,v_2)$ 并且$v_1\neq u_2$.本文刻画了有向多重图类$\mathcal{H}_1$和$\mathcal{H}_2$,并证明了一个有向多重图$D$的跳图$J(D)$是强连通的当且仅当$D\not\in \mathcal{H}_1$.特别地, $J(D)$是弱连通的当且仅当$D\not\in \mathcal{H}_2$.进一步, 得到以下结果: (i) 存在有向多重图类$\mathcal{D}$使得有向多重图$D$的强连通跳图$J(D)$是强迹连通的当且仅当$D\not\in\mathcal{D}$. (ii) 每一个有向多重图$D$的强连通跳图$J(D)$是弱迹连通的,因此是超欧拉的. (iii) 每一个有向多重图D的弱连通跳图$J(D)$含有生成迹. 相似文献
10.
通过对子图和围长的研究,完全刻画了直径为3的3-正则简单平面图,获得了这类图仅有的11个非同构图. 相似文献
11.
Raymond Viglione 《Acta Appl Math》2008,104(2):173-176
Let q be a prime power,
the field of q elements, and n≥1 a positive integer. The Wenger graph W
n
(q) is defined as follows: the vertex set of W
n
(q) is the union of two copies P and L of (n+1)-dimensional vector spaces over
, with two vertices (p
1,p
2,…,p
n+1)∈P and [l
1,l
2,…,l
n+1]∈L being adjacent if and only if l
i
+p
i
=p
1
l
i−1 for 2≤i≤n+1. Graphs W
n
(q) have several interesting properties. In particular, it is known that when connected, their diameter is at most 2n+2. In this note we prove that the diameter of connected Wenger graphs is 2n+2 under the assumption that 1≤n≤q−1. 相似文献
12.
Let R be a ring with nonzero identity. The unit graph of R, denoted by G(R), has its set of vertices equal to the set of all elements of R; distinct vertices x and y are adjacent if and only if x + y is a unit of R. In this article, the basic properties of G(R) are investigated and some characterization results regarding connectedness, chromatic index, diameter, girth, and planarity of G(R) are given. (These terms are defined in Definitions and Remarks 4.1, 5.1, 5.3, 5.9, and 5.13.) 相似文献
13.
14.
Stephen E. Wright 《代数通讯》2013,41(6):1987-1991
Short, elementary proofs of the optimal bounds for various path and cycle lengths are given for the zero-divisor graphs and digraphs of semigroups. 相似文献
15.
16.
Hadwiger's conjecture asserts that every graph with chromatic number t contains a complete minor of order t. Given integers , the Kneser graph is the graph with vertices the k‐subsets of an n‐set such that two vertices are adjacent if and only if the corresponding k‐subsets are disjoint. We prove that Hadwiger's conjecture is true for the complements of Kneser graphs. 相似文献
17.
Let R be a commutative ring with unity. The cozero-divisor graph of R, denoted by Γ′(R), is a graph with vertex set W*(R), where W*(R) is the set of all nonzero and nonunit elements of R, and two distinct vertices a and b are adjacent if and only if a ? Rb and b ? Ra, where Rc is the ideal generated by the element c in R. Recently, it has been proved that for every nonlocal finite ring R, Γ′(R) is a unicyclic graph if and only if R ? ?2 × ?4, ?3 × ?3, ?2 × ?2[x]/(x 2). We generalize the aforementioned result by showing that for every commutative ring R, Γ′(R) is a unicyclic graph if and only if R ? ?2 × ?4, ?3 × ?3, ?2 × ?2[x]/(x 2), ?2[x, y]/(x, y)2, ?4[x]/(2x, x 2). We prove that for every positive integer Δ, the set of all commutative nonlocal rings with maximum degree at most Δ is finite. Also, we classify all rings whose cozero-divisor graph has maximum degree 3. Among other results, it is shown that for every commutative ring R, gr(Γ′(R)) ∈ {3, 4, ∞}. 相似文献
18.
关于3连通图的容错直径和宽直径 总被引:5,自引:0,他引:5
容错直径和宽直径是度量网络可靠性和有效性的重要参数.对任意k连通图,它的容错直径Dk不超过宽直径dk,本证明:当D2=2时,d3≤max{D, l,2D3-2};当D2≥3时,d3≤(D2-1)[2(D2-1)(D3-1)-D2-2] 1. 相似文献
19.
Mark S. MacLean 《Journal of Algebraic Combinatorics》2003,17(2):125-147
Let denote a bipartite distance-regular graph with diameter D 4, valency k 3, and distinct eigenvalues 0 > 1 > ··· > D. Let M denote the Bose-Mesner algebra of . For 0 i D, let E
i denote the primitive idempotent of M associated with
i
. We refer to E
0 and E
D as the trivial idempotents of M. Let E, F denote primitive idempotents of M. We say the pair E, F is taut whenever (i) E, F are nontrivial, and (ii) the entry-wise product E F is a linear combination of two distinct primitive idempotents of M. We show the pair E, F is taut if and only if there exist real scalars , such that
i + 1
i + 1 –
i – 1
i – 1 =
i
(
i + 1 –
i – 1) +
i
(
i + 1 –
i – 1) + (1 i D – 1)where 0, 1, ...,
D
and 0, 1, ...,
D
denote the cosine sequences of E, F, respectively. We define to be taut whenever has at least one taut pair of primitive idempotents but is not 2-homogeneous in the sense of Nomura and Curtin. Assume is taut and D is odd, and assume the pair E, F is taut. We show
for 1 i D – 1, where = 1, = 1. Using these equations, we recursively obtain 0, 1, ..., D and 0, 1, ...,
D
in terms of the four real scalars , , , . From this we obtain all intersection numbers of in terms of , , , . We showed in an earlier paper that the pair E
1, E
d is taut, where d = (D – 1)/2. Applying our results to this pair, we obtain the intersection numbers of in terms of k, , 1, d, where denotes the intersection number c
2. We show that if is taut and D is odd, then is an antipodal 2-cover. 相似文献
20.
Matthias Kriesell 《Graphs and Combinatorics》2006,22(4):481-485
Let κ(G) denote the (vertex) connectivity of a graph G. For ℓ≥0, a noncomplete graph of finite connectivity is called ℓ-critical if κ(G−X)=κ(G)−|X| for every X⊆V(G) with |X|≤ℓ.
Mader proved that every 3-critical graph has diameter at most 4 and asked for 3-critical graphs having diameter exceeding
2. Here we give an affirmative answer by constructing an ℓ-critical graph of diameter 3 for every ℓ≥3. 相似文献