The crossing number of K5,n+1∖e Huang, Yuanqiu; Wang, Yuxi
Applied mathematics and computation,
07/2020, Volume:
376
Journal Article
Peer reviewed
Let K5,n+1∖e (n ≥ 0) denote the complete bipartite graph K5,n+1 with one edge deleted. In this paper, we show that the crossing number of K5,n+1∖e is n(n−1).
The extremal problem of two types of high order spectra for graphs are considered, which are called r-adjacency spectrum and t-clique spectrum, respectively. In this paper, we obtain the maximum ...r-adjacency spectral radius of a Kr+1 minor-free graph of order n in the case 1≤r≤3, which implies the Hadwiger’s conjecture is true for 1≤r≤3. Moreover, an upper bound of the 3-clique spectral radius of a Bk-free and K2,l-free graph G of order n is given, where Bk is the graph consisting of k triangles sharing an edge. As a corollary of this result, we obtain an upper bound of the number of the triangles for G which improves a result of Alon and Shikhelman (2016).
In this corrigendum, we correct some errors in the proof of Theorem 2.1 in “On the conjecture of Sombor energy of a graph” Examples and Counterexamples 3 (2023) 100115.
The weak saturation number of K2,t Miralaei, Meysam; Mohammadian, Ali; Tayfeh-Rezaie, Behruz
Discrete mathematics,
September 2024, Volume:
347, Issue:
9
Journal Article
Peer reviewed
For two graphs G and F, we say that G is weakly F-saturated if G has no copy of F as a subgraph and one can join all the nonadjacent pairs of vertices of G in some order so that a new copy of F is ...created at each step. The weak saturation number wsat(n,F) is the minimum number of edges of a weakly F-saturated graph on n vertices. In this paper, we examine wsat(n,Ks,t), where Ks,t is the complete bipartite graph with parts of sizes s and t. We determine wsat(n,K2,t) for all n⩾t+2 which particularly corrects a previous report in the literature. It is also shown that wsat(s+t,Ks,t)=(s+t−12) if gcd(s,t)=1 and wsat(s+t,Ks,t)=(s+t−12)+1 otherwise.
•Recently, many papers investigated the effects on distance energy by deleting an edge from a complete multipartite graph. In this paper, we determine the effects on distance energy by embedding one ...or more than one edges into a complete bipartite graph. The method involving the information of elements of some eigenvectors is also suitable to a complete multipartite graph and therefore an analogous result may be obtained.
The distance energy of a connected graph G is defined to be E(G)=∑i=1n|λi(G)|, where λ1(G),…,λn(G) are distance eigenvalues of G. Recently, much research has explored the change of distance energy of a complete multipartite graph by deleting an edge. In this paper, we investigate the effect of distance energy of a complete bipartite graph by embedding some edges. An analogous result on a complete multipartite graph also holds.
The generalized k-connectivity κk(G) of a graph G, introduced by Hager in 1985, is a natural generalization of the concept of connectivity κ(G), which is just for k=2. Rongxia Hao et al. determined ...the generalized 4-connectivity of the total graphs of the complete equipartition bipartite graph and conjectured that κ4(T(Km,m+1))=2m−1 and κ4(T(Km,n))=2m for n>m+1 and m≥4 in Appl. Math. Comput. 422 (2022). In this paper, we solved this conjecture.
The list r-hued coloring of Km,n Tang, Meng; Liu, Fengxia; Lai, Hong-Jian
Discrete Applied Mathematics,
05/2024, Volume:
348
Journal Article
Peer reviewed
Let L be list assignment of colors available for vertices of a graph G. An (L,r)-coloring of G is a proper coloring c such that for any vertex v∈V(G), we have c(v)∈L(v) and ∣c(NG(v))∣≥ min{dG(v),r}. ...The list r-hued chromatic number of G, denoted as χL,r(G), is the least integer k, such that for list assignment L satisfying ∣L(v)∣=k, for any v∈V(G), G has an (L,r)-coloring. Let Km,n denote a complete bipartite graph. In Discrete Math. 306(16)(2006) 1997–2004, it has been proved if n≥m≥2, then χr(Km,n)=min{2r,n+m,r+m}. In this paper, we determine the list r-hued chromatic number of Km,n.
We determine the minimum number of crossings in an outerplanar drawing of the complete bipartite graph Km,n for any values of m and n, which was known only for the specific case when m|n. Moreover, ...we provide a one-to-one correspondence (up to equivalence) between the outerplanar and cylindrical drawings of the complete bipartite graph that preserves the number of crossings but not the crossings themselves.
We investigate the terminal-pairability problem in the case when the base graph is a complete bipartite graph, and the demand graph is a (not necessarily bipartite) multigraph on the same vertex set. ...In computer science, this problem is known as the edge-disjoint paths problem. We improve the lower bound on the maximum value of Δ(D) which still guarantees that the demand graph D has a realization in Kn,n. We also solve the extremal problem on the number of edges, i.e., we determine the maximum number of edges which guarantees that a demand graph is realizable in Kn,n.
Finding the smallest number of crosscaps that suffice to orientation-embed every edge signature of the complete bipartite graph Km,n is an open problem. In this paper that number for the complete ...bipartite graph K4,n, n≥4, is determined by using diamond products of signed graphs. The number is 2⌊n−12⌋+1, which is attained by K4,n with exactly 1 negative edge, except that when n=4, the number is 4, which is attained by K4,4 with exactly 4 independent negative edges.
PDF