二部图的单特征值

一个图的特征值通常指的是它的邻接矩阵的特征值,在图的所有特征值中,重数为1的特征值即所谓的单特征值具有特殊的重要性.确定一个图的单特征值是一个比较困难的问题,主要是没有一个通用的方法.1969年,Petersdorf和Sachs给出了点传递图单特征值的取值范围,但是对于具体的点传递图还需要根据图本身的特性来确定它的单特...     

Chaotic Numbers of Complete Bipartite Graphs and Tripartite Graphs

In this paper, we study the chaotic numbers of complete bipartite graphs and complete tripartite graphs. For the complete bipartite graphs, we find closed-form formulas of the chaotic numbers and characterize all chaotic mappings. For the complete tripartite graphs, we develop an algorithm running in O(n ⁴ ₃) time to find the chaotic numbers, with n ₃ the number of vertices in the largest partite set.Research supported by NSC 90-2115-M-036-003.The author thanks the authors of Ref. 6, since his work was motivated by their work. Also, the author thanks the referees for helpful comments which made the paper more readable.     

偶匹配可扩性的极图问题(英文)

设G是含有完美匹配的简单图.称图G是偶匹配可扩的(BM-可扩的),如果G的每一个导出子图是偶图的匹配M都可以扩充为一个完美匹配.极图问题是图论的核心问题之一.本文将刻画极大偶匹配不可扩图,偶图图类和完全多部图图类中的极大偶匹配可扩图.     

Bipartite Subgraphs of Graphs with Maximum Degree Three

We prove that for a connected graph G with maximum degree 3 there exists a bipartite subgraph of G containing almost of the edges of G. Furthermore, we completely characterize the set of all extremal graphs, i.e. all connected graphs G=(V, E) with maximum degree 3 for which no bipartite subgraph has more than of the edges; |E| denotes the cardinality of E. For 2-edge-connected graphs there are two kinds of extremal graphs which realize the lower bound . Received: July 17, 1995 / Revised: April 5, 1996     

Domination in Bipartite Graphs and in Their Complements

The domatic numbers of a graph G and of its complement $\bar G$ were studied by J. E. Dunbar, T. W. Haynes and M. A. Henning. They suggested four open problems. We will solve the following ones: Characterize bipartite graphs G having $d\left( G \right) = d\left( {\bar G} \right)$ Further, we will present a partial solution to the problem: Is it true that if G is a graph satisfying $d\left( G \right) = d\left( {\bar G} \right)$ then $\gamma \left( G \right) = \gamma \left( {\bar G} \right)$ ? Finally, we prove an existence theorem concerning the total domatic number of a graph and of its complement     

Unbalanced Star-Factorizations of Complete Bipartite Graphs II

There are simple arithmetic conditions necessary for the complete bipartite graph K_m,n to have a complete factorization by subgraphs which are made up of disjoint copies of K_p,q. It is conjectured that these conditions are also sufficient. In any factor the copies of K_p,q have two orientations depending which side of the bipartition the p-set lies. The balance ratio is the relative proportion, x:y of these where gcd(x,y)=1. In this paper, we continue the study of the unbalanced case (y > x) where p = 1, to show that the conjecture is true whenever y is sufficiently large. We also prove the conjecture for K_1,4-factorizations.     

二部图中的独立6-圈

本文主要证明了对二部图G=(V_1,V_2,E),|V_1|=|V_2|=3k,其中k为正整数.若G的最小度至少为2k-1,则G至少包含k-1个独立6-圈.     

由圈长分布确定的偶图

阶为n的图G的圈长分布是序列(C1，C2，…，Cn)，其中ci是图G中长为i的圈数．本文得到如下结果：设A∈_E(Kn,r)，|A|≤1，且n≤r≤min{n 6，2n-3)，则G=Kn,r，r-A是由它的圈长分布确定的．     

Decomposition of Complete Bipartite Even Graphs into Closed Trails

We prove that any complete bipartite graph K _a,b , where a, b are even integers, can be decomposed into closed trails with prescribed even lengths.     

On the Jump Number Problem in Hereditary Classes of Bipartite Graphs

We prove a necessary condition for polynomial solvability of the jump number problem in classes of bipartite graphs characterized by a finite set of forbidden induced bipartite subgraphs. For some classes satisfying this condition, we propose polynomial algorithms to solve the jump number problem.     

关于定向二部图的得分

我们研究了定向二部图的得分表偶,并且得到了关于非负整数表偶是某个定向二部图的得分表偶的一个刻划。     

任意n个完备二分图的并图的k－优美性和算术性

证明了对于正整数k,n,si,ti（si,ti≥2,i=1,2,…,n）,图n/U/i=1,Ksi,ti是k-优美图;对于正整数k,d（d≥2）,k≠0（roodd）及n,si,ti（si,ti≥2,i=1,2,…,n）,图n/U/i=1,Ksi,ti是（k,d）-算术图,前一结论推广了文[6]的相应结果。     

On the Nullity of Bipartite Graphs

The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. We obtain some lower bounds for the nullity of graphs and we then find the nullity of bipartite graphs with no cycle of length a multiple of 4 as a subgraph. Among bipartite graphs on n vertices, the star has the greatest nullity (equal to n − 2). We generalize this by showing that among bipartite graphs with n vertices, e edges and maximum degree Δ which do not have any cycle of length a multiple of 4 as a subgraph, the greatest nullity is . G. R. Omidi: This research was in part supported by a grant from IPM (No.87050016).     

极大3限制边连通二部图的充分条件

设G=(V,E)是一个连通图.称一个边集合S■E是一个k限制边割,如果G-S的每个连通分支至少有k个顶点.称G的所有k限制边割中所含边数最少的边割的基数为G的k限制边连通度,记为λ_k(G).定义ξ_k(G)=min{[X,■]:|X|=k,G[X]连通,■=V(G)\X}.称图G是极大k限制边连通的,如果λ_k(G)=ξ_k(G).本文给出了围长为g>6的极大3限制边连通二部图的充分条件.     

Remarks on Vertex-Distinguishing IE-Total Coloring of Complete Bipartite Graphs K4,n and Kn,n

Let G be a simple graph.An IE-total coloring f of G refers to a coloring of the vertices and edges of G so that no two adjacent vertices receive the same color.Let C(u) be the set of colors of vertex u and edges incident to u under f.For an IE-total coloring f of G using k colors,if C(u)=C(v) for any two different vertices u and v of V(G),then f is called a k-vertex-distinguishing IE-total-coloring of G,or a k-VDIET coloring of G for short.The minimum number of colors required for a VDIET coloring of G is denoted by χ ie vt (G),and it is called the VDIET chromatic number of G.We will give VDIET chromatic numbers for complete bipartite graph K4,n (n≥4),K n,n (5≤ n ≤ 21) in this article.     

On the Decomposition of Graphs into Complete Bipartite Graphs

In a complete bipartite decomposition π of a graph, we consider the number ϑ(v;π) of complete bipartite subgraphs incident with a vertex v. Let ϑ(G)= ϑ(v;π). In this paper the exact values of ϑ(G) for complete graphs and hypercubes and a sharp upper bound on ϑ(G) for planar graphs are provided, respectively. An open problem proposed by P.C. Fishburn and P.L. Hammer is solved as well.     

Some Bipartite Ramsey Numbers

Consider a complete bipartite graph K(s, s) with p = 2s points. Let each line of the graph have either red or blue colour. The smallest number p of points such that K(s, s) always contains red K(m, n) or blue K(m, n) is called bipartite Ramsey number denoted by rb(K(m, n), K(m, n)). In this paper, we show that

Small Worlds Among Interlocking Directors: Network Structure and Distance in Bipartite Graphs

We describe a methodology to examine bipartite relational data structures as exemplified in networks of corporate interlocking. These structures can be represented as bipartite graphs of directors and companies, but direct comparison of empirical datasets is often problematic because graphs have different numbers of nodes and different densities. We compare empirical bipartite graphs to simulated random graph distributions conditional on constraints implicit in the observed datasets. We examine bipartite graphs directly, rather than simply converting them to two 1-mode graphs, allowing investigation of bipartite statistics important to connection redundancy and bipartite connectivity. We introduce a new bipartite clustering coefficient that measures tendencies for localized bipartite cycles. This coefficient can be interpreted as an indicator of inter-company and inter-director closeness; but high levels of bipartite clustering have a cost for long range connectivity. We also investigate degree distributions, path lengths, and counts of localized subgraphs. Using this new approach, we compare global structural properties of US and Australian interlocking company directors. By comparing observed statistics against those from the simulations, we assess how the observed graphs are structured, and make comparisons between them relative to the simulated graph distributions. We conclude that the two networks share many similarities and some differences. Notably, both structures tend to be influenced by the clustering of directors on boards, more than by the accumulation of board seats by individual directors; that shared multiple board memberships (multiple interlocks) are an important feature of both infrastructures, detracting from global connectivity (but more so in the Australian case); and that company structural power may be relatively more diffuse in the US structure than in Australia.     

关于k-消去二分图的一些结果

图 G的一个 k-正则支撑子图称为 G的 k-因子 ,若对 G的任一边 e,图 G- e总存在一个 k-因子 ,则称 G是 k-消去图 .证明了二分图 G=( X,Y) ,且 | X | =| Y|是 k-消去图的充分必要条件是 k| S|≤ r1 + 2 r2 +…+ k( rk+… + rΔ) - ε( S)对所有 S X成立 .并由此给出二分图是 k-消去图的充分度条件 .     

Ovoids and Bipartite Subgraphs in Generalized Quadrangles

A point-line incidence system is called an -partial geometry of order (s,t) if each line contains s + 1 points, each point lies on t + 1 lines, and for any point a not lying on a line L, there exist precisely lines passing through a and intersecting L (the notation is pG (s,t)). If = 1, then such a geometry is called a generalized quadrangle and denoted by GQ(s,t). It is established that if a pseudogeometric graph for a generalized quadrangle GQ(s,s ² – s) contains more than two ovoids, then s = 2. It is proved that the point graph of a generalized quadrangle GQ(4,t) contains no K _4,6-subgraphs. Finally, it is shown that if some -subgraph of a pseudogeometric graph for a generalized quadrangle GQ(4,t) contains a triangle, then t 6.