共查询到20条相似文献,搜索用时 15 毫秒
1.
Let V, E, and D denote the cardinality of the vertex set, the cardinality of the edge set, and the maximum degree of a bipartite multigraph G. We show that a minimal edge-coloring of G can be computed in O(E logD time. This result follows from an algorithm for finding a matching in a regular bipartite graph in O(E) time. Received September 23, 1999 相似文献
2.
By End(G) and hEnd(G) we denote the set of endomorphisms and half-strong endomorphisms of a graph G respectively. A graph G is said to be E-H-unretractive if End(G) = hEnd(G). A general characterization of an E-H-unretractive graph seems to be difficult. In this paper, bipartite graphs with E-H-unretractivity are characterized explicitly. 相似文献
3.
Maximal Energy Bipartite Graphs 总被引:1,自引:0,他引:1
Given a graph G, its energy E(G) is defined to be the sum of the absolute values of the eigenvalues of G. This quantity is used in chemistry to approximate the total π-electron energy of molecules and in particular, in case G is bipartite, alternant hydrocarbons. Here we show that if G is a bipartite graph with n vertices, then
must hold, characterize those bipartite graphs for which this bound is sharp, and provide an infinite family of maximal energy
bipartite graphs.
Received: December 1, 2000 Final version received: August 28, 2001
RID="*"
ID="*" The author thanks the Swedish Natural Science Research Council (NFR) – grant M12342-300 – for its support.
Acknowledgments. The authors would like to thank Ivan Gutman for encouraging them to write this paper, and for helpful discussions on this
topic. They also would like to thank Edwin van Dam for his reference concerning connected bipartite regular graphs with four
eigenvalues. 相似文献
4.
5.
6.
Let e(m, n), o(m, n), bsc(m, n) be the number of unlabelled bipartite graphs with an even number of edges whose partite sets have m vertices and n vertices, the number of those with an odd number of edges, and the number of unlabelled bipartite self-complementary graphs whose partite sets have m vertices and n vertices, respectively. Then this paper shows that the equality bsc(m, n) = e(m, n) ? o(m, n) holds. 相似文献
7.
Domenico Labbate 《Designs, Codes and Cryptography》2004,32(1-3):267-275
The amalgamation technique has been introduced for groups by Higman et al. [8] and Goldschmidt [7] and developed on geometries by Kegel and Schleiermacher [9]. We define a “graph amalgam” to point out a different approach to certain classes of cubic bipartite graphs. Furthermore, we find relations between graph amalgams, 3-bridges and star-products of cubic bipartite graphs. 相似文献
8.
Michael S. Lang 《European Journal of Combinatorics》2002,23(8):1015
Let Γ denote a bipartite distance-regular graph with diameterD ≥ 4 and valency k ≥ 3. Let θ 0 > θ 1 > > θD denote the eigenvalues of Γ and let E0, E1, , EDdenote the associated primitive idempotents. Fix s(1 ≤ s ≤ D − 1 ) and abbreviate E: = Es. We say E is a tail whenever the entrywise product E E is a linear combination of E0, E and at most one other primitive idempotent of Γ. Letqijσi + 1 h (0 ≤ h , i, j ≤ D) denote the Krein parameters of Γ and letΔ denote the undirected graph with vertices 0, 1, , D where two vertices i, j are adjacent whenever i ≠ = j andqijσi + 1s ≠ = 0. We show E is a tail if and only if one of (i)–(iii) holds: (i) Δ is a path; (ii) Δ has two connected components, each of which is a path; (iii) D = 6 and Δ has two connected components, one of which is a path on four vertices and the other of which is a clique on three vertices. 相似文献
9.
Robert S. Strichartz 《Journal of Fourier Analysis and Applications》2016,22(5):1157-1173
On a bipartite graph G we consider the half sampling problem of uniquely recovering a function from its values on the even vertices, under the appropriate half bandlimited assumption with respect to a Laplacian on the graph. We discuss both finite and infinite graphs, give the appropriate definition of “half bandlimited” that involves splitting the mid frequency, and give an explicit solution to the problem. We discuss in detail the example of a regular tree. We also consider a related sampling problem on graphs that are generated by edge substitution. 相似文献
10.
Order - Let κ be a successor cardinal. We prove that consistently every bipartite graph of size κ+ × κ+ contains either an independent set or a clique of size τ ×... 相似文献
11.
N. P. Chiang 《Journal of Optimization Theory and Applications》2006,131(3):485-491
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
4
3) time to find the chaotic numbers, with n
3 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. 相似文献
12.
The Ramsey number r(H, K
n
) is the smallest positive integer N such that every graph of order N contains either a copy of H or an independent set of size n. The Turán number ex(m, H) is the maximum number of edges in a graph of order m not containing a copy of H. We prove the following two results: (1) Let H be a graph obtained from a tree F of order t by adding a new vertex w and joining w to each vertex of F by a path of length k such that any two of these paths share only w. Then r(H,Kn) £ ck,t [(n1+1/k)/(ln1/k n)]{r(H,K_n)\leq c_{k,t}\, {n^{1+1/k}\over \ln^{1/k} n}} , where c
k,t
is a constant depending only on k and t. This generalizes some results in Li and Rousseau (J Graph Theory 23:413–420, 1996), Li and Zang (J Combin Optim 7:353–359,
2003), and Sudakov (Electron J Combin 9, N1, 4 pp, 2002). (2) Let H be a bipartite graph with ex(m, H) = O(m
γ
), where 1 < γ < 2. Then r(H,Kn) £ cH ([(n)/(lnn)])1/(2-g){r(H,K_n)\leq c_H ({n\over \ln n})^{1/(2-\gamma)}}, where c
H
is a constant depending only on H. This generalizes a result in Caro et al. (Discrete Math 220:51–56, 2000). 相似文献
13.
A ‘bipartite characteristic’ parameter is defined for bipartite graphs that mimics the (Euler) characteristic—the number of vertices, minus the number of edges, plus the number of triangles, minus the number of 4-cliques, etc.—of general graphs. This allows the characterization of linear, totally balanced, acyclic, tree, and biacyclic hypergraphs in terms of the bipartite characteristic values of their incidence graphs. 相似文献
14.
Emre Kolotoğlu 《组合设计杂志》2013,21(11):524-530
A decomposition of a complete graph into disjoint copies of a complete bipartite graph is called a ‐design of order n. The existence problem of ‐designs has been completely solved for the graphs for , for , K2, 3 and K3, 3. In this paper, I prove that for all , if there exists a ‐design of order N, then there exists a ‐design of order n for all (mod ) and . Giving necessary direct constructions, I provide an almost complete solution for the existence problem for complete bipartite graphs with fewer than 18 edges, leaving five orders in total unsolved. 相似文献
15.
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. 相似文献
16.
Interval minors of bipartite graphs were recently introduced by Jacob Fox in the study of Stanley–Wilf limits. We investigate the maximum number of edges in ‐interval minor‐free bipartite graphs. We determine exact values when and describe the extremal graphs. For , lower and upper bounds are given and the structure of ‐interval minor‐free graphs is studied. 相似文献
17.
Let G be a bipartite graph with bicoloration {A, B}, |A| = |B|, and let w : E(G) K where K is a finite abelian group with k elements. For a subset S E(G) let
. A Perfect matching M E(G) is a w-matching if w(M) = 1.A characterization is given for all w's for which every perfect matching is a w-matching.It is shown that if G = K
k+1,k+1 then either G has no w-matchings or it has at least 2 w-matchings.If K is the group of order 2 and deg(a) d for all a
A, then either G has no w-matchings, or G has at least (d – 1)! w-matchings.R. Meshulam: Research supported by a Technion V.P.R. Grant No. 100-854. 相似文献
18.
The boxicity of a graph G is defined as the minimum integer k such that G is an intersection graph of axis-parallel k-dimensional boxes. Chordal bipartite graphs are bipartite graphs that do not contain an induced cycle of length greater than
4. It was conjectured by Otachi, Okamoto and Yamazaki that chordal bipartite graphs have boxicity at most 2. We disprove this
conjecture by exhibiting an infinite family of chordal bipartite graphs that have unbounded boxicity. 相似文献
19.
Inspired by connections described in a recent paper by Mark L. Lewis, between the common divisor graph Γ(X) and the prime vertex graph Δ(X), for a set X of positive integers, we define the bipartite divisor graph B(X), and show that many of these connections flow naturally from properties of B(X). In particular we establish links between parameters of these three graphs, such as number and diameter of components, and
we characterise bipartite graphs that can arise as B(X) for some X. Also we obtain necessary and sufficient conditions, in terms of subconfigurations of B(X), for one of Γ(X) or Δ(X) to contain a complete subgraph of size 3 or 4. 相似文献
20.
Amotz Bar-Noy Guy Kortsarz 《Journal of Algorithms in Cognition, Informatics and Logic》1998,28(2):339-365
The problem ofminimum color sumof a graph is to color the vertices of the graph such that the sum (average) of all assigned colors is minimum. Recently it was shown that in general graphs this problem cannot be approximated withinn1 − ε, for any ε > 0, unlessNP = ZPP(Bar-Noyet al., Information and Computation140(1998), 183–202). In the same paper, a 9/8-approximation algorithm was presented for bipartite graphs. The hardness question for this problem on bipartite graphs was left open. In this paper we show that the minimum color sum problem for bipartite graphs admits no polynomial approximation scheme, unlessP = NP. The proof is byL-reducing the problem of finding the maximum independent set in a graph whose maximum degree is four to this problem. This result indicates clearly that the minimum color sum problem is much harder than the traditional coloring problem, which is trivially solvable in bipartite graphs. As for the approximation ratio, we make a further step toward finding the precise threshold. We present a polynomial 10/9-approximation algorithm. Our algorithm uses a flow procedure in addition to the maximum independent set procedure used in previous solutions. 相似文献