Total Vertex Irregularity Strength of Dense Graphs

Consider a graph of minimum degree δ and order n. Its total vertex irregularity strength is the smallest integer k for which one can find a weighting such that for every pair of vertices of G. We prove that the total vertex irregularity strength of graphs with is bounded from above by . One of the cornerstones of the proof is a random ordering of the vertices generated by order statistics.     

Bipartite Graphs Whose Edge Algebras Are Complete Intersections

Let R be a monomial subalgebra of k[x₁,…,x_N] generated by square free monomials of degree two. This paper addresses the following question: when is R a complete intersection? For such a k-algebra we can associate a graph G whose vertices are x₁,…,x_N and whose edges are {(x_i, x_j)|x_ix_j  R}. Conversely, for any graph G with vertices {x₁,…,x_N} we define the edge algebra associated with G as the subalgebra of k[x₁,…,x_N] generated by the monomials {x_ix_j|(x_i, x_j) is an edge of G}. We denote this monomial algebra by k[G]. This paper describes all bipartite graphs whose edge algebras are complete intersections.     

Total Edge Irregularity Strength of Toroidal Fullerene

A toroidal fullerene (toroidal polyhex) is a cubic bipartite graph embedded on the torus such that each face is a hexagon. An edge irregular total k-labeling of a graph G is such a labeling of the vertices and edges with labels 1, 2, … , k that the weights of any two different edges are distinct, where the weight of an edge is the sum of the label of the edge itself and the labels of its two endvertices. The minimum k for which the graph G has an edge irregular total k-labeling is called the total edge irregularity strength, tes(G). In this paper we determine the exact value of the total edge irregularity strength of toroidal polyhexes.     

Decomposition of Complete Graphs into Isomorphic Complete Bipartite Graphs

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 , K_{2, 3} and K_{3, 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.     

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.     

Interval Minors of Complete Bipartite Graphs

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.     

Signed Roman (Total) Domination Numbers of Complete Bipartite Graphs and Wheels

A signed(res. signed total) Roman dominating function, SRDF(res.STRDF) for short, of a graph G =(V, E) is a function f : V → {-1, 1, 2} satisfying the conditions that(i)∑v∈N[v]f(v) ≥ 1(res.∑v∈N(v)f(v) ≥ 1) for any v ∈ V, where N [v] is the closed neighborhood and N(v) is the neighborhood of v, and(ii) every vertex v for which f(v) =-1 is adjacent to a vertex u for which f(u) = 2. The weight of a SRDF(res. STRDF) is the sum of its function values over all vertices.The signed(res. signed total) Roman domination number of G is the minimum weight among all signed(res. signed total) Roman dominating functions of G. In this paper,we compute the exact values of the signed(res. signed total) Roman domination numbers of complete bipartite graphs and wheels.     

Coloring Complete and Complete Bipartite Graphs from Random Lists

Assign to each vertex v of the complete graph \(K_n\) on n vertices a list L(v) of colors by choosing each list independently and uniformly at random from all f(n)-subsets of a color set \([n] = \{1,\dots , n\}\), where f(n) is some integer-valued function of n. Such a list assignment L is called a random (f(n), [n])-list assignment. In this paper, we determine the asymptotic probability (as \(n \rightarrow \infty \)) of the existence of a proper coloring \(\varphi \) of \(K_n\), such that \(\varphi (v) \in L(v)\) for every vertex v of \(K_n\). We show that this property exhibits a sharp threshold at \(f(n) = \log n\). Additionally, we consider the corresponding problem for the line graph of a complete bipartite graph \(K_{m,n}\) with parts of size m and n, respectively. We show that if \(m = o(\sqrt{n})\), \(f(n) \ge 2 \log n\), and L is a random (f(n), [n])-list assignment for the line graph of \(K_{m,n}\), then with probability tending to 1, as \(n \rightarrow \infty \), there is a proper coloring of the line graph of \(K_{m,n}\) with colors from the lists.     

Ramsey Numbers of Some Bipartite Graphs Versus Complete Graphs

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,K_n) ￡ c_k,t [(n^1+1/k)/(ln^1/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,K_n) ￡ c_H ([(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).     

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.     

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.     

Multicolor Ramsey Numbers For Complete Bipartite Versus Complete Graphs

Let be graphs. The multicolor Ramsey number is the minimum integer r such that in every edge‐coloring of by k colors, there is a monochromatic copy of in color i for some . In this paper, we investigate the multicolor Ramsey number , determining the asymptotic behavior up to a polylogarithmic factor for almost all ranges of t and m. Several different constructions are used for the lower bounds, including the random graph and explicit graphs built from finite fields. A technique of Alon and Rödl using the probabilistic method and spectral arguments is employed to supply tight lower bounds. A sample result is for any t and m, where c₁ and c₂ are absolute constants.     

The k-Restricted Edge Connectivity of Balanced Bipartite Graphs

For a connected graph G = (V, E), an edge set S ì E{S\subset E} is called a k-restricted edge cut if G − S is disconnected and every component of G − S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λ _k (G), is defined as the cardinality of a minimum k-restricted edge cut. For two disjoint vertex sets U₁,U₂ ì V(G){U_1,U_2\subset V(G)}, denote the set of edges of G with one end in U ₁ and the other in U ₂ by [U ₁, U ₂]. Define x_k(G)=min{|[U,V(G)\ U]|: U{\xi_k(G)=\min\{|[U,V(G){\setminus} U]|: U} is a vertex subset of order k of G and the subgraph induced by U is connected}. A graph G is said to be λ _k -optimal if λ _k (G) = ξ _k (G). A graph is said to be super-λ _k if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k. In this paper, we present some degree-sum conditions for balanced bipartite graphs to be λ _k -optimal or super-λ _k . Moreover, we demonstrate that our results are best possible.     

Nowhere‐Zero Flows on Signed Complete and Complete Bipartite Graphs

Bouchet's conjecture asserts that each signed graph which admits a nowhere‐zero flow has a nowhere‐zero 6‐flow. We verify this conjecture for two basic classes of signed graphs—signed complete and signed complete bipartite graphs by proving that each such flow‐admissible graph admits a nowhere‐zero 4‐flow and we characterise those which have a nowhere‐zero 2‐flow and a nowhere‐zero 3‐flow.     

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.     

Bounds on Ramsey Numbers of Certain Complete Bipartite Graphs

Bounds on the Ramsey number r(K_l,m,K_l,n), where we may assume l ≤ m ≤ n, are determined for 3 ≤ l ≤ 5 and m ≈ n. Particularly, for m = n the general upper bound on r(K_l,n, K_l,n) due to Chung and Graham is improved for those l. Moreover, the behavior of r(K_3,m, K_3,n) is studied for m fixed and n sufficiently large.     

Binomial Edge Ideals of Complete Multipartite Graphs

In this article, we prove some results about the binomial edge ideal J _G of a complete r-partite graph G = K _{a 1,…, a r} : (1) characterization of unmixedness of J _G and Cohen–Macaulayness of the residue ring S/J _G , (2) F-purity of S/J _G , and (3) the equality of the symbolic and the ordinary powers of J _G .     

On the Number of Genus Embeddings of Complete Bipartite Graphs

In this paper, on the basis of joint tree model introduced by Liu, by dividing the associated surfaces into segments layer by layer, we show that there are at least ${C_{1}\cdot C_{2}^{\frac{m}{2}}\cdot C_{3}^{\frac{n}{2}}(m-1)^{m-\frac{1}{2}}(n-1)^{n-\frac{1}{2}}}$ distinct genus embeddings for complete bipartite graph K _m,n , where C ₁, C ₂, and C ₃ are constants depending on the residual class of m modular 4 and that of n modular 4.