Search

In 1964, Moon extended Cayley's formula to a nice expression of the number of spanning trees in complete graphs containing any fixed spanning forest. After nearly 60 years, Dong and the first author discovered the second Moon-type formula: an explicit formula of the number of spanning trees in complete bipartite graphs containing any fixed spanning forest. Followed this direction, Li, Chen and Yan found the Moon-type formula for complete 3- and 4-partite graphs. These are the only families of graphs that have the corresponding Moon-type formulas. In this paper, we first determine resistance distances in the vertex-weighted complete split graph S m , n ω. Then we obtain the Moon-type formula for the vertex-weighted complete split graph S m , n ω , that is, the weighted spanning tree enumerator of S m , n ω containing any fixed spanning forest. [ABSTRACT FROM AUTHOR]

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 K r + 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 B k -free and K 2 , l -free graph G of order n is given, where B k 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). [ABSTRACT FROM AUTHOR]

Given two graphs G,H $G,H$ and a positive integer q $q$, an (H,q) $(H,q)$‐coloring of G $G$ is an edge‐coloring of G $G$ such that every copy of H $H$ in G $G$ receives at least q $q$ distinct colors. The bipartite Erdős–Gyárfás function r(Kn,n,Ks,t,q) $r({K}_{n,n},{K}_{s,t},q)$ is defined to be the minimum number of colors needed for Kn,n ${K}_{n,n}$ to have a (Ks,t,q) $({K}_{s,t},q)$‐coloring. For balanced complete bipartite graphs Kp,p ${K}_{p,p}$, the function r(Kn,n,Kp,p,q) $r({K}_{n,n},{K}_{p,p},q)$ was studied systematically in Axenovich et al. In this paper, we study the asymptotic behavior of this function for complete bipartite graphs Ks,t ${K}_{s,t}$ that are not necessarily balanced. Our main results deal with thresholds and lower and upper bounds for the growth rate of this function, in particular for (sub)linear and (sub)quadratic growth. We also obtain new lower bounds for the balanced bipartite case, and improve several results given by Axenovich, Füredi and Mubayi. Our proof techniques are based on an extension to bipartite graphs of the recently developed Color Energy Method by Pohoata and Sheffer and its refinements, and a generalization of an old result due to Corrádi. [ABSTRACT FROM AUTHOR]

In this paper, based on the Diophantine equation technique, we first prove the circulant graph C (Z n , { k 1 , k 2 }) is isomorphic to the disjoint union of gcd (n , k 1 , k 2) identical graphs, which belong to one of the three types of graphs: (i) C (Z n { 1 , k }) ; (i i) the Cartesian graph bundle C s □ φ C t over cycles; (i i i) the Cartesian product of the complete graph K 2 and a cycle. Naturally, to study the dispersability of C (Z n , { k 1 , k 2 }) can be reduced to study that of the above three types. Next, we solve the dispersability of the circulant graph C (Z n , { 1 , k }). Specifically, C (Z n , { 1 , k }) is dispersable if it is a bipartite; otherwise, it is nearly dispersable. In addition, we prove that bipartite circulant graphs are dispersable. [ABSTRACT FROM AUTHOR]

Given positive integers k ≤ d and a finite field F , a set S ⊂ F d is (k, c)-subspace evasive if every k-dimensional affine subspace contains at most c elements of S. By a simple averaging argument, the maximum size of a (k, c)-subspace evasive set is at most c | F | d - k . When k and d are fixed, and c is sufficiently large, the matching lower bound Ω (| F | d - k) is proved by Dvir and Lovett. We provide an alternative proof of this result using the random algebraic method. We also prove sharp upper bounds on the size of (k, c)-evasive sets in case d is large, extending results of Ben-Aroya and Shinkar. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. We show that the minimum number of k-dimensional linear hyperplanes needed to cover the grid [ n ] d ⊂ R d is Ω d (n d (d - k) d - 1 ) , which matches the upper bound proved by Balko et al., and settles a problem proposed by Brass et al. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in R d assuming their incidence graph avoids the complete bipartite graph K c , c for some large constant c = c (d) . [ABSTRACT FROM AUTHOR]

The concept of Roman domination has been a subject of intrigue for more than two decades, with the fundamental Roman domination problem standing out as one of the most significant challenges in this field. This article studies a practically motivated generalization of this problem, known as the k-strong Roman domination. In this problem variant, defenders within a network are tasked with safeguarding any k vertices simultaneously, under multiple attacks. The aim is to find a feasible mapping that assigns a (integer) weight to each vertex of the input graph with a minimum sum of weights across all vertices. A function is considered feasible if any non-defended vertex, i.e. one labeled by zero, is protected by at least one of its neighboring vertices labeled by at least two. Furthermore, each defender ensures the safety of a non-defended vertex by imparting a value of one to it while retaining a one for themselves. To the best of our knowledge, this paper represents the first theoretical study on this problem. The study presents results for general graphs, establishes connections between the problem at hand and other domination problems, and provides exact values and bounds for specific graph classes, including complete graphs, paths, cycles, complete bipartite graphs, grids, and a few selected classes of convex polytopes. Additionally, an attainable lower bound for general cubic graphs is provided. [ABSTRACT FROM AUTHOR]

Rainbow antimagic coloring is the combination of antimagic labeling and rainbow coloring. The smallest number of colors induced from all edge weights of antimagic labeling is the rainbow antimagic connection number of G , denoted by rac (G). Given a graph G with vertex set V (G) and edge set E (G) , the function f from V (G) to { 1 , 2 , ... , | V (G) | } is a bijective function. The associated weight of an edge y z ∈ E (G) under f is w (y z) = f (y) + f (z). A path R in the vertex-labeled graph G is said to be a rainbow y − z path if for any two edges y z , y ′ z ′ ∈ E (R) it satisfies w (y z) ≠ w (y ′ z ′). The function f is called a rainbow antimagic labeling of G if there exists a rainbow y − z path for every two vertices y , z ∈ V (G). When we assign each edge y z with the color of the edge weight w (y z) , we say the graph G admits a rainbow antimagic coloring. In this paper, we show the new lower bound and exact value of the rainbow antimagic connection number of comb product of any tree and complete bipartite graph. [ABSTRACT FROM AUTHOR]

The concepts of domination and topological index hold great significance within the realm of graph theory. Therefore, it is pertinent to merge these concepts to derive the domination index of a graph. A novel concept of the domination index is introduced, which utilizes the domination degree of a vertex. The domination degree of a vertex a is defined as the minimum cardinality of a minimal dominating set (MDS) that includes a. Methods to find a MDS containing a particular vertex is also discussed in the study. The notion of domination degree and domination index are studied for graphs like complete graphs, complete bipartite, r − partite graphs, cycles, wheels, paths, book graphs, windmill graphs, Kragujevac trees. The study is extended to operation in graphs. Inequalities involving domination degree and already established graph parameters are discussed. An application of domination degree is discussed in facility allocation in a city. [ABSTRACT FROM AUTHOR]

We prove that for any r∈N$r\in \mathbb {N}$, there exists a constant Cr$C_r$ such that the following is true. Let F={F1,F2,⋯}$\mathcal {F}=\lbrace F_1,F_2,\dots \rbrace$ be an infinite sequence of bipartite graphs such that |V(Fi)|=i$|V(F_i)|=i$ and Δ(Fi)⩽Δ$\Delta (F_i)\leqslant \Delta$ hold for all i$i$. Then, in any r$r$‐edge‐coloured complete graph Kn$K_n$, there is a collection of at most exp(CrΔ)$\exp (C_r\Delta)$ monochromatic subgraphs, each of which is isomorphic to an element of F$\mathcal {F}$, whose vertex sets partition V(Kn)$V(K_n)$. This proves a conjecture of Corsten and Mendonça in a strong form and generalises results on the multi‐colour Ramsey numbers of bounded‐degree bipartite graphs. It also settles the bipartite case of a general conjecture of Grinshpun and Sárközy. [ABSTRACT FROM AUTHOR]

In this paper we determine the pair difference cordial number of degree splitting graph of bistar, complete bipartite graph, ladder, wheel. [ABSTRACT FROM AUTHOR]

In this paper, we use semidefinite programming and representation theory to compute new lower bounds on the crossing number of the complete bipartite graph K m , n , extending a method from de Klerk et al. (SIAM J Discrete Math 20:189–202, 2006) and the subsequent reduction by De Klerk, Pasechnik and Schrijver (Math Prog Ser A and B 109:613–624, 2007). We exploit the full symmetry of the problem using a novel decomposition technique. This results in a full block-diagonalization of the underlying matrix algebra, which we use to improve bounds on several concrete instances. Our results imply that cr (K 10 , n) ≥ 4.87057 n 2 - 10 n , cr (K 11 , n) ≥ 5.99939 n 2 - 12.5 n , cr (K 12 , n) ≥ 7.25579 n 2 - 15 n , cr (K 13 , n) ≥ 8.65675 n 2 - 18 n for all n. The latter three bounds are computed using a new and well-performing relaxation of the original semidefinite programming bound. This new relaxation is obtained by only requiring one small matrix block to be positive semidefinite. [ABSTRACT FROM AUTHOR]

Given a graph L $L$, the Turán number ex(n,L) $\text{ex}(n,L)$ is the maximum possible number of edges in an n $n$‐vertex L $L$‐free graph. The study of Turán number of graphs is a central topic in extremal graph theory. Although the celebrated Erdős‐Stone‐Simonovits theorem gives the asymptotic value of ex(n,L) $\text{ex}(n,L)$ for nonbipartite L $L$, it is challenging in general to determine the exact value of ex(n,L) $\text{ex}(n,L)$ for χ(L)≥3 $\chi (L)\ge 3$. The odd‐ballooning of H $H$ is a graph such that each edge of H $H$ is replaced by an odd cycle and all new vertices of odd cycles are distinct. Here the length of odd cycles is not necessarily equal. The exact value of Turán number of the odd‐ballooning of H $H$ is previously known for H $H$ being a cycle, a path, a tree with assumptions, and K2,3 ${K}_{2,3}$. In this paper, we manage to obtain the exact value of Turán number of the odd‐ballooning of Ks,t ${K}_{s,t}$ with 2≤s≤t $2\le s\le t$, where (s,t)∉{(2,2),(2,3)} $(s,t)\notin \{(2,2),(2,3)\}$ and each odd cycle has length at least five. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V (G) and edge set E(G). For a set M of vertices and an edge e of a graph G, let P (M, e) be the set of pairs (x, y) with a vertex x of M and a vertex y of V (G) such that dG(x, y) ≠dG−e(x, y). Given a vertex x, an edge e is said to be monitored by x if there exists a vertex v in G such that (x, v) ∈P ({x}, e), and the collection of such edges is EM(x). A set M of vertices of a graph G is distance-edge-monitoring (DEM for short) set if every edge e of G is monitored by some vertex of M, that is, the set P (M, e) is nonempty. The DEM number dem(G) of a graph G is defined as the smallest size of such a set in G. The vertices of M represent distance probes in a network modeled by G; when the edge e fails, the distance from x to y increases, and thus we are able to detect the failure. In this paper, we first give some bounds or exact values of line graphs of trees, grids, complete bipartite graphs, and obtain the exact values of DEM numbers for some graphs and their line graphs, including the friendship and wheel graphs. Next, for each n, m > 1, we obtain that there exists a graph Gn,m such that dem(Gn,m) = n and dem(L(Gn,m)) = 4 or 2n + t, for each integer t≥ 0. In the end, the DEM number for the line graph of a small-world network (DURT) is given. [ABSTRACT FROM AUTHOR]

The conditional fractional matching preclusion number (CFMP number for short) fmp1(G) of a graph G is the minimum number of edges whose deletion results in a graph without isolated vertices and without fractional perfect matchings. In this paper, we study the CFMP number of complete graphs, complete bipartite graphs and twisted cubes. Also, we give Nordhaus–Gaddum-type results for the CFMP numbers of general graphs. [ABSTRACT FROM AUTHOR]

The problem of Zarankiewicz asks for the maximum number of edges in a bipartite graph on n vertices which does not contain the complete bipartite graph K k , k as a subgraph. A classical theorem due to Kővári, Sós, and Turán says that this number of edges is O n 2 - 1 / k . An important variant of this problem is the analogous question in bipartite graphs with VC-dimension at most d, where d is a fixed integer such that k ≥ d ≥ 2 . A remarkable result of Fox et al. (J. Eur. Math. Soc. (JEMS) 19:1785–1810, 2017) with multiple applications in incidence geometry shows that, under this additional hypothesis, the number of edges in a bipartite graph on n vertices and with no copy of K k , k as a subgraph must be O n 2 - 1 / d . This theorem is sharp when k = d = 2 , because by design any K 2 , 2 -free graph automatically has VC-dimension at most 2, and there are well-known examples of such graphs with Ω n 3 / 2 edges. However, it turns out this phenomenon no longer carries through for any larger d. We show the following improved result: the maximum number of edges in bipartite graphs with no copies of K k , k and VC-dimension at most d is o (n 2 - 1 / d) , for every k ≥ d ≥ 3 . [ABSTRACT FROM AUTHOR]

In crisp graph theory, there are numerous topological indices accessible, including the Misbalance Prodeg Index, which is one of the most well-known degree-based topological indexes. In crisp graphs, both vertices and edges have membership values of 1 or 0, whereas in fuzzy graphs, both vertices and edges have different memberships. This is an entire contrast to the crisp graph. In this paper, we introduce the Fuzzy Misbalance Prodeg Index of a fuzzy graph, which is a generalized form of the Misbalance Prodeg Index of a graph. We find bounds of this index and find bounds of certain classes of graphs such as path graph, cycle graph, complete graph, complete bipartite graph, and star graph. We give an algorithm to find the Fuzzy Misbalance Prodeg Index of a graph for the model of multi-criteria decision-making is established. We present applications from daily life in multi-criteria decision-making. We apply our obtained model of the Fuzzy Misbalance Prodeg Index for the multicriteria decision-making to the choice of the best supplier and we also show the graphical analysis of our index with the other indices that show how our index is better than other existing indices. [ABSTRACT FROM AUTHOR]

Copyright of Journal of Central China Normal University is the property of Huazhong Normal University and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

We continue the study of (tw , ω) -bounded graph classes, that is, hereditary graph classes in which the treewidth can only be large due to the presence of a large clique, with the goal of understanding the extent to which this property has useful algorithmic implications for the Maximum Independent Set and related problems. In the previous paper of the series [Dallard, Milanič, and Štorgel, Treewidth versus clique number. II. Tree-independence number, J. Comb. Theory, Ser. B, 164 (2024) 404–442], we introduced the tree-independence number , a min-max graph invariant related to tree decompositions. Bounded tree-independence number implies both (tw , ω) -boundedness and the existence of a polynomial-time algorithm for the Maximum Weight Independent Packing problem, provided that the input graph is given together with a tree decomposition with bounded independence number. In particular, this implies polynomial-time solvability of the Maximum Weight Independent Set problem. In this paper, we consider six graph containment relations—the subgraph, topological minor, and minor relations, as well as their induced variants—and for each of them characterize the graphs H for which any graph excluding H with respect to the relation admits a tree decomposition with bounded independence number. The induced minor relation is of particular interest: we show that excluding either a K 5 minus an edge or the 4-wheel implies the existence of a tree decomposition in which every bag is a clique plus at most 3 vertices, while excluding a complete bipartite graph K 2 , q implies the existence of a tree decomposition with independence number at most 2 (q − 1). These results are obtained using a variety of tools, including ℓ -refined tree decompositions, SPQR trees, and potential maximal cliques, and actually show that in the bounded cases identified in this work, one can also compute tree decompositions with bounded independence number efficiently. Applying the algorithmic framework provided by the previous paper in the series leads to polynomial-time algorithms for the Maximum Weight Independent Set problem in an infinite family of graph classes, each of which properly contains the class of chordal graphs. In particular, these results apply to the class of 1-perfectly orientable graphs, answering a question of Beisegel, Chudnovsky, Gurvich, Milanič, and Servatius from 2019. [ABSTRACT FROM AUTHOR]

A graph is O k -free if it does not contain k pairwise vertex-disjoint and non-adjacent cycles. We prove that "sparse" (here, not containing large complete bipartite graphs as subgraphs) O k -free graphs have treewidth (even, feedback vertex set number) at most logarithmic in the number of vertices. This is optimal, as there is an infinite family of O 2 -free graphs without K 2 , 3 as a subgraph and whose treewidth is (at least) logarithmic. Using our result, we show that Maximum Independent Set and 3-Coloring in O k -free graphs can be solved in quasi-polynomial time. Other consequences include that most of the central NP-complete problems (such as Maximum Independent Set , Minimum Vertex Cover , Minimum Dominating Set , Minimum Coloring) can be solved in polynomial time in sparse O k -free graphs, and that deciding the O k -freeness of sparse graphs is polynomial time solvable. [ABSTRACT FROM AUTHOR]

This paper investigates a leader–follower consensus problem of multi-layer networks and understands the role of leader's allocations in the process of consensus. Leader–follower coherence quantified by the spectrum measures the extent of consensus between leaders and followers in the system under additive noise. In order to study the exact interplay between leader–follower coherence and leader's allocations, we choose complete multi-partite networks as network models and assign the leaders into different layers. Based on the network construction, we obtain exact solutions of leader–follower coherence with freely assigned leaders and reveal that the allocations of leaders have a significant impact on the coherence. Finally, we compare the leader–follower coherence and leaderless coherence of bipartite networks when the number of leaders and network size satisfies certain conditions. [ABSTRACT FROM AUTHOR]

We construct 2-step nilpotent Lie algebras using labeled directed simple graphs and give a criterion to detect certain ideals and subalgebras by finding special subgraphs. We prove that if a label occurs only once, then reversing its orientation leads to an isomorphic algebra. As a consequence, if every edge is labeled differently, the Lie algebra depends only on the underlying undirected graph. In addition, we construct the graphs of all 2-step nilpotent Lie algebras of dimension ≤ 6 and compute the algebra of strata preserving derivations of the Lie algebra associated with the complete bipartite graph K m , n with two different labelings. [ABSTRACT FROM AUTHOR]

In 1975, Erd̋s asked the following question: What is the maximum number of edges that an |$n$| -vertex graph can have without containing a cycle with all diagonals? Erd̋s observed that the upper bound |$O(n^{5/3})$| holds since the complete bipartite graph |$K_{3,3}$| can be viewed as a cycle of length six with all diagonals. In this paper, we resolve this old problem. We prove that there exists a constant |$C$| such that every |$n$| -vertex graph with at least |$Cn^{3/2}$| edges contains a cycle with all diagonals. Since any cycle with all diagonals contains cycles of length four, this bound is best possible using well-known constructions of graphs without four-cycles based on finite geometry. Among other ideas, our proof involves a novel lemma about finding an almost-spanning robust expander, which might be of independent interest. [ABSTRACT FROM AUTHOR]

Since Grover developed a quantum search algorithm for unstructured data, generalizing the algorithm to structured datasets, which can be represented as graphs, has been an important research topic. Recently, Krovi et al. introduced a quantum algorithm that can find a marked vertex on any ergodic and reversible graph by using absorbing marked vertices, replacing the marked vertices with partially absorbing vertices. The algorithm was extended to finding marked vertices in any graph with multiple marked vertices using the quantum fast-forwarding technique (QFF). However, the proof of this result based on QFF does not provide much intuition about the underlying mechanism. In this paper, to obtain the underlying mechanism of the quantum search with absorbing marked vertices, we consider, as a nontrivial example, the complete bipartite graph consisting of two sets X 1 and X 2 with the marked vertices being on both vertex sets. By analytically finding the spectral information of the quantum walk, we propose an approximate optimal search parameter s o . We demonstrate that the quantum algorithm at the optimal search parameter s o shows a quadratic speedup compared to the corresponding classical search method if the number of marked vertices is smaller than the total number of vertices. Additionally, we find that the quantum search is described in terms of a two-state model for that case. [ABSTRACT FROM AUTHOR]

A simple undirected regular graph is said to be semisymmetric if it is edge-transitive but not vertex-transitive. For a semisymmetric graph Γ of order 2 p 3 , p a prime, it is well known that Γ is bipartite with two biparts having equal size. The complete classification of such graphs has been given for the full automorphism group Aut (Γ) acting unfaithfully on at least one bipart of Γ , which shows that there is only one infinite family of such graphs with valency p 2. The graphs of this kind have been determined when Aut (Γ) acts faithfully and primitively on at least one bipart of Γ , and thus there is only one remaining case for classifying such graphs of valency p 2 , Aut (Γ) acting faithfully and imprimitively on both biparts of Γ , which is dealt with in this paper. As a result, there is only one infinite family of semisymmetric graphs of order 2 p 3 with valency p 2. [ABSTRACT FROM AUTHOR]

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 (N G (v)) ∣ ≥ min { d G (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 K m , n denote a complete bipartite graph. In [Discrete Math. 306(16)(2006) 1997–2004], it has been proved if n ≥ m ≥ 2 , then χ r (K m , n) =min { 2 r , n + m , r + m }. In this paper, we determine the list r -hued chromatic number of K m , n. [ABSTRACT FROM AUTHOR]

The Jump graph J(G) of a graph G is the graph whose vertices are edges of G and two vertices of J(G) are adjacent if and only if they are not adjacent in G. Equivalently complement of line graph L(G) is the Jump graph J(G) of G. In this paper, we give characterization for the Jump graph of cycles into Monotonic star decomposition. Also we give characterization for the Jump graph of complete bipartite graphs into even decomposition. [ABSTRACT FROM AUTHOR]

An Italian dominating function of a graph G = (V , E) with vertex set V is defined as a function f : V → { 0 , 1 , 2 } , which satisfies the condition that for every v ∈ V with f (v) = 0 , ∑ u ∈ N (v) f (u) ≥ 2. The weight of an Italian dominating function on G is the sum f (V) = ∑ u ∈ V f (v) and the Italian dominating number, and γ I (G) indicates the minimum weight of an Italian dominating function f. In this paper, the structure of the generalized Sierpiński networks is investigated using the bounds of Italian domination number of graphs and the methods of mathematical induction and reduction to absurdity. Then, the Italian domination on the generalized Sierpiński networks S (G , t) is obtained, where G denotes any special class of Path P n , Cycle C n , Wheel W n , Star K 1 , n , and complete bipartite graph K m , n . [ABSTRACT FROM AUTHOR]

We consider the minimum spanning tree problem on a weighted complete bipartite graph $K_{n_R, n_B}$ whose $n=n_R+n_B$ vertices are random, i.i.d. uniformly distributed points in the unit cube in $d$ dimensions and edge weights are the $p$ -th power of their Euclidean distance, with $p\gt 0$. In the large $n$ limit with $n_R/n \to \alpha _R$ and $0\lt \alpha _R\lt 1$ , we show that the maximum vertex degree of the tree grows logarithmically, in contrast with the classical, non-bipartite, case, where a uniform bound holds depending on $d$ only. Despite this difference, for $p\lt d$ , we are able to prove that the total edge costs normalized by the rate $n^{1-p/d}$ converge to a limiting constant that can be represented as a series of integrals, thus extending a classical result of Avram and Bertsimas to the bipartite case and confirming a conjecture of Riva, Caracciolo and Malatesta. [ABSTRACT FROM AUTHOR]

In this paper, we introduced a new graph polynomial called the vertex geodetic closure polynomial of a graph and established results for paths, complete bipartite graphs, and graphs resulting from the join of two graphs. [ABSTRACT FROM AUTHOR]

The biclique partition number of a graph G, denoted by bp(G), is the minimum number of complete bipartite subgraphs are needed to be representing all edges of G. A graph G is called an eigensharp graph if it is satisfying bp(G) = max{i-(A(G)), i+(A(G))} where i-(A(G)) and i+(A(G)) are the number of negative and positive eigenvalues of the adjacency matrix of G, respectively. In this paper, we are interested in studying some special graphs in terms of having the property of eigensharp. We show that the barbell graph, the sun graph, the friendship graph and their complements have the property of eigensharp. [ABSTRACT FROM AUTHOR]

What are the unavoidable induced subgraphs of graphs with large treewidth? It is well‐known that the answer must include a complete graph, a complete bipartite graph, all subdivisions of a wall and line graphs of all subdivisions of a wall (we refer to these graphs as the "basic treewidth obstructions"). So it is natural to ask whether graphs excluding the basic treewidth obstructions as induced subgraphs have bounded treewidth. Sintiari and Trotignon answered this question in the negative. Their counterexamples, the so‐called "layered wheels," contain wheels, where a wheel consists of a hole (i.e., an induced cycle of length at least four) along with a vertex with at least three neighbors in the hole. This leads one to ask whether graphs excluding wheels and the basic treewidth obstructions as induced subgraphs have bounded treewidth. This also turns out to be false due to Davies' recent example of graphs with large treewidth, no wheels and no basic treewidth obstructions as induced subgraphs. However, in Davies' example there exist holes and vertices (outside of the hole) with two neighbors in them. Here we prove that a hole with a vertex with at least two neighbors in it is inevitable in graphs with large treewidth and no basic obstruction. Our main result is that graphs in which every vertex has at most one neighbor in every hole (that does not contain it) and with the basic treewidth obstructions excluded as induced subgraphs have bounded treewidth. [ABSTRACT FROM AUTHOR]

The distance energy of a connected graph G is the sum of absolute values of the eigenvalues of the distance matrix of G. In this paper, we study how the distance energy of the complete split graph G S (m , n) = K m + K ¯ n changes when an edge is deleted from it. The complete split graph G S (m , n) consists of a clique on m vertices and an independent set on n vertices in which each vertex of the clique is adjacent to each vertex of the independent set. We prove that the distance energy of the complete split graph G S (m , n) always increases when an edge is deleted from it. [ABSTRACT FROM AUTHOR]

Graph protection using mobile guards has received a lot of attention in the literature. It has been considered in different forms, including Eternal Dominating set, Eternal Independent set and Eternal Vertex Cover set. In this paper, we introduce and study two new models of graph protection, namely Eternal Feedback Vertex Sets (EFVS) and m-Eternal Feedback Vertex Sets (m-EFVS). Both models are based on an initial selection of a feedback vertex set (FVS), where a vertex in FVS can be replaced with a neighboring vertex such that the resulting set is a FVS too. We prove bounds for both the eternal and m-eternal feedback vertex numbers on, mainly, distance graphs, circulant graphs and grids. Also, we deduce other inequalities for both parameters on cycles, complete graphs and complete bipartite graphs. [ABSTRACT FROM AUTHOR]

We studied radio labelings of graphs in response to the Channel Assignment Problem (CAP). In a graph G, the radio labeling is a mapping ϖ: V(G) → {0, 1, 2,..., }, such as |ϖ(μ') - ϖ(μ")| ≥ diam(G)+1-d(μ', μ"). The label of μ for under ϖ is defined by the integer ϖ(μ), and the span under is defined by span(ϖ) = max{|ϖ(μ') - ϖ(μ")|: μ', μ&" ∈ V(G)}. rn(G) = minϖspan(ϖ) is defined as the radio number of G when the minimum over all radio labeling ϖ of G is taken. G is said to be optimal if its radio labeling is span(ϖ) = rn(G). A graph H is said to be an m super subdivision if G is replaced by the complete bipartite graph Km,m with m = 2 in such a way that the end vertices of the edge are merged with any two vertices of the same partite set X or Y of Km,m after removal of the edge of G. Up to this point, many lower and upper bounds of rn(G) have been found for several kinds of graph families. This work presents a comprehensive analysis of the radio number rn(G) for a graph G, with particular emphasis on the m super subdivision of a path Pn with n(n ≥ 3) vertices, along with a complete bipartite graph Km,m consisting of m v/ertices, where m = 2. [ABSTRACT FROM AUTHOR]

Motivated by bipartite Gallai–Ramsey type problems, we consider edge-colorings of complete bipartite graphs without rainbow tree and matching. Given two graphs G and H , and a positive integer k , define the bipartite Gallai–Ramsey number bgr k (G : H) as the minimum number of vertices n such that n 2 ≥ k and for every N ≥ n , any coloring (using all k colors) of the complete bipartite graph K N , N contains a rainbow copy of G or a monochromatic copy of H. In this paper, we first describe the structures of a complete bipartite graph K n , n without rainbow P 4 + and 3 K 2 , respectively, where P 4 + is the graph consisting of a P 4 with one extra edge incident with an interior vertex. Furthermore, we determine the exact values or upper and lower bounds on bgr k (G : H) when G is a 3-matching or a 4-path or P 4 + , and H is a bipartite graph. [ABSTRACT FROM AUTHOR]

Paintability of graphs, which is also called online choosability of graphs, was introduced by Schauz and by Zhu in 2009, and has been studied in point of the difference from choosability of graphs. Compared with the choice number and the chromatic number, it is much more difficult to determine the paint number of a given graph. For example, even the 3-paintable complete bipartite graphs have not been characterized yet. In this paper, we focus on the paintability of complete bipartite graphs, especially m -paintability of K m + 1 , r. Let r OL (m) denote the least integer r such that K m + 1 , r is not m -paintable. In this paper, we determine the order of r OL (m) as r OL (m) = Θ (m m − 1). Let r (m) denote the least r such that K m + 1 , r is not m -choosable, for which Hoffman and Johnson Jr. determined as r (m) = m m − (m − 1) m = Θ (m m). As a corollary, we can show that r OL (m) / r (m) tends to 0 when m goes to infinity. [ABSTRACT FROM AUTHOR]

Centrality measurement plays an important role to identify important/influential vertices and edges in a network or graph from different points of view. It also provide invaluable insights into the structure and functioning of interconnected systems, enabling researchers to identify critical nodes for targeted interventions, predict network behaviors, and optimize network performance. Though there are different centrality measurements in graphs theory, yet closeness centrality is widely used to analyze biological networks, social networks, fuzzy social network, transportation networks, etc. The closeness centrality of a node x in a network/graph is the unit fraction whose denominator is the sum of the distances from x to other nodes. This paper presents theoretical development to compute the closeness centrality of each node/vertex of different corona product graphs between well known graph (path graph, complete graph, cycle graph, wheel graph, star graph and complete bipartite graph) and general graph. Corona graph has lots of applications in signed networks, biotechnology, chemistry, small-world network, etc. We also present a suitable real application of our proposed results by which we can identify the influential nodes in small-world network. [ABSTRACT FROM AUTHOR]

Broadcasting is a fundamental problem in the information dissemination area. In classical broadcasting, a message must be sent from one network member to all other members as rapidly as feasible. Although it has been demonstrated that this problem is NP-Hard for arbitrary graphs, it has several applications in various fields. As a result, the universal lists model, replicating real-world restrictions like the memory limits of nodes in large networks, is introduced as a branch of this problem in the literature. In the universal lists model, each node is equipped with a fixed list and has to follow the list regardless of the originator. In this study, we focus on the non-adaptive branch of universal lists broadcasting. In this regard, we establish the optimal broadcast time of k -ary trees and binomial trees under the non-adaptive model and provide an upper bound for complete bipartite graphs. We also improved a general upper bound for trees under the same model and showed that our upper bound cannot be improved in general. [ABSTRACT FROM AUTHOR]

We consider the following problem: for a given graph G and two integers k and d, can we apply a fixed graph operation at most k times in order to reduce a given graph parameter π by at least d? We show that this problem is NP-hard when the parameter is the independence number and the graph operation is vertex deletion or edge contraction, even for fixed d = 1 and when restricted to chordal graphs. We give a polynomial time algorithm for bipartite graphs when the operation is edge contraction, the parameter is the independence number and d is fixed. Further, we complete the complexity dichotomy for H-free graphs when the parameter is the clique number and the operation is edge contraction by showing that this problem is NP-hard in (C 3 + P 1) -free graphs even for fixed d = 1 . When the operation is edge deletion and the parameter is the chromatic number, we determine the computational complexity of the associated problem for cographs and complete multipartite graphs. Our results answer several open questions stated in Diner et al. (Theor Comput Sci 746:49–72, 2012, https://doi.org/10.1016/j.tcs.2018.06.023). [ABSTRACT FROM AUTHOR]

Two subgraphs A , B of a graph G are anticomplete if they are vertex-disjoint and there are no edges joining them. Is it true that if G is a graph with bounded clique number, and sufficiently large chromatic number, then it has two anticomplete subgraphs, both with large chromatic number? This is a question raised by El-Zahar and Erdős in 1986, and remains open. If so, then at least there should be two anticomplete subgraphs both with large minimum degree, and that is one of our results. We prove two variants of this. First, a strengthening: we can ask for one of the two subgraphs to have large chromatic number: that is, for all t , c ≥ 1 there exists d ≥ 1 such that if G has chromatic number at least d , and does not contain the complete graph K t as a subgraph, then there are anticomplete subgraphs A , B , where A has minimum degree at least c and B has chromatic number at least c. Second, we look at what happens if we replace the hypothesis that G has sufficiently large chromatic number with the hypothesis that G has sufficiently large minimum degree. This, together with excluding K t , is not enough to guarantee two anticomplete subgraphs both with large minimum degree; but it works if instead of excluding K t we exclude the complete bipartite graph K t , t. More exactly: for all t , c ≥ 1 there exists d ≥ 1 such that if G has minimum degree at least d , and does not contain the complete bipartite graph K t , t as a subgraph, then there are two anticomplete subgraphs both with minimum degree at least c. [ABSTRACT FROM AUTHOR]

In this paper, we obtain necessary and sufficient conditions for decomposing tensor product of complete graphs into some connected unicyclic bipartite graphs with eight edges. [ABSTRACT FROM AUTHOR]

A subgraph of an edge-colored graph is rainbow if all of its edges have different colors. Given a graph family G and a graph H , the anti-Ramsey number A R (G , H) is the maximum number of colors in an edge-coloring of a graph G ∈ G which has no rainbow copy of H. When G = { G } , we write A R (G , H) for short. Erdős, Simonovits and Sós introduced these numbers in the 1970s, they studied the case when G is a complete graph. Since then, many results have appeared considering G and H belonging to specific graph classes. In particular, Jendrol', Schiermeyer and Tu (Jendrol' et al., 2014) obtained an upper bound for A R (T n , k K 2) in terms of n and k for k ≥ 3 and n ≥ 2 k , where T n is the family of maximal planar graphs on n vertices. Jin and Ye (Jin and Ye, 2018) continued the study of anti-Ramsey numbers of matchings in planar graphs, by deriving an upper bound for A R (M n , k K 2) , where M n is the family of maximal outerplanar graphs on n vertices. In both works, examples are shown for which there are colorings using many colors while avoiding rainbow matchings, but the numbers of colors in these examples do not reach the upper bounds. The bounds of A R (T n , k K 2) were improved in following works by other researchers. This paper goes in the same direction of these two works, proving exact value for A R (B n , k K 2) in terms of n and k for n ≥ 6 and k ≥ 3 , where B n is the family of maximal bipartite outerplanar graphs on n vertices which contains a Hamilton cycle. [ABSTRACT FROM AUTHOR]

Given a graph $H$ , let us denote by $f_\chi (H)$ and $f_\ell (H)$ , respectively, the maximum chromatic number and the maximum list chromatic number of $H$ -minor-free graphs. Hadwiger's famous colouring conjecture from 1943 states that $f_\chi (K_t)=t-1$ for every $t \ge 2$. A closely related problem that has received significant attention in the past concerns $f_\ell (K_t)$ , for which it is known that $2t-o(t) \le f_\ell (K_t) \le O(t (\!\log \log t)^6)$. Thus, $f_\ell (K_t)$ is bounded away from the conjectured value $t-1$ for $f_\chi (K_t)$ by at least a constant factor. The so-called $H$ -Hadwiger's conjecture, proposed by Seymour, asks to prove that $f_\chi (H)={\textrm{v}}(H)-1$ for a given graph $H$ (which would be implied by Hadwiger's conjecture). In this paper, we prove several new lower bounds on $f_\ell (H)$ , thus exploring the limits of a list colouring extension of $H$ -Hadwiger's conjecture. Our main results are: For every $\varepsilon \gt 0$ and all sufficiently large graphs $H$ we have $f_\ell (H)\ge (1-\varepsilon)({\textrm{v}}(H)+\kappa (H))$ , where $\kappa (H)$ denotes the vertex-connectivity of $H$. For every $\varepsilon \gt 0$ there exists $C=C(\varepsilon)\gt 0$ such that asymptotically almost every $n$ -vertex graph $H$ with $\left \lceil C n\log n\right \rceil$ edges satisfies $f_\ell (H)\ge (2-\varepsilon)n$. The first result generalizes recent results on complete and complete bipartite graphs and shows that the list chromatic number of $H$ -minor-free graphs is separated from the desired value of $({\textrm{v}}(H)-1)$ by a constant factor for all large graphs $H$ of linear connectivity. The second result tells us that for almost all graphs $H$ with superlogarithmic average degree $f_\ell (H)$ is separated from $({\textrm{v}}(H)-1)$ by a constant factor arbitrarily close to $2$. Conceptually these results indicate that the graphs $H$ for which $f_\ell (H)$ is close to the conjectured value $({\textrm{v}}(H)-1)$ for $f_\chi (H)$ are typically rather sparse. [ABSTRACT FROM AUTHOR]

The complex adjacency matrix A C (G) for a multidigraph G is introduced in Barik and Sahoo (AKCE Int J Graphs Comb 17(1):466–479, 2020). We study the rank of multidigraphs corresponding to the complex adjacency matrix and call it A C -rank. It is known that a connected graph G has rank 2 if and only if G is a complete bipartite graph, and has rank 3 if and only if it is a complete tripartite graph (Cheng in Electron J Linear Algebra 16:60–67, 2007). We observe that these results hold as special cases for multidigraphs but are not sufficient. In this article, we characterize all multidigraphs with A C -rank 2 and 3, respectively. [ABSTRACT FROM AUTHOR]

Let d-claw (or d-star) stand for K 1 , d , the complete bipartite graph with 1 and d ≥ 1 vertices on each part. The d-claw vertex deletion problem, d -claw-vd, asks for a given graph G and an integer k if one can delete at most k vertices from G such that the resulting graph has no d-claw as an induced subgraph. Thus, 1 -claw-vd and 2 -claw-vd are just the famous vertex cover problem and the cluster vertex deletion problem, respectively. In this paper, we strengthen a hardness result recently proved in Jena and Subramani (in: Du, Du, Wu, and Zhu (eds) Theory and applications of models of computation - 17th annual conference, TAMC 2022, Tianjin, China, September 16–18, 2022, Proceedings, 2022), by showing that cluster vertex deletion remains NP -complete even when restricted to planar bipartite graphs of maximum degree 3 and arbitrary large girth. Moreover, for every d ≥ 3 , we show that d -claw-vd is NP -complete even when restricted to planar bipartite graphs of maximum degree d. These hardness results are optimal with respect to degree constraint. By extending the hardness result in Bonomo-Braberman et al (in: Computing and combinatorics - 26th international conference, COCOON 2020, Proceedings, Lecture Notes in Computer Science, vol 12273, Springer, 2020, pp 14–26, 2020), we show that, for every d ≥ 3 , d -claw-vd is NP -complete even when restricted to split graphs without (d + 1) -claws, and split graphs of diameter 2. On the positive side, we prove that d -claw-vd is polynomially solvable on what we call d-block graphs, a class properly contains all block graphs. This result extends the polynomial-time algorithm in Cao et al (Theor Comput Sci, 2018) for 2 -claw-vd on block graphs to d -claw-vd for all d ≥ 2 and improves the polynomial-time algorithm proposed by Bonomo-Brabeman et al. for (unweighted) 3 -claw-vd on block graphs to 3-block graphs. [ABSTRACT FROM AUTHOR]

Let r≥2 $r\ge 2$ and let F $F$ be an (r+1) $(r+1)$ ‐chromatic graph with a color‐critical edge, that is, there exists e∈E(F) $e\in E(F)$ such that F−e $F-e$ has chromatic number r $r$. Gerbner recently conjectured that every n $n$ ‐vertex maximal F $F$ ‐free graph with at least (1−1r)n22−o(nr+1r) $(1-\frac{1}{r})\frac{{n}^{2}}{2}-o({n}^{\frac{r+1}{r}})$ edges contains an induced complete r $r$ ‐partite graph on n−o(n) $n-o(n)$ vertices. Let Fs,k ${F}_{s,k}$ be a graph obtained from s $s$ copies of C2k+1 ${C}_{2k+1}$ by sharing a common edge. In this paper, we show that for all k≥2 $k\ge 2$ if G $G$ is an n $n$ ‐vertex maximal Fs,k ${F}_{s,k}$ ‐free graph with at least n2∕4−o(ns+2s+1) ${n}^{2}\unicode{x02215}4-o({n}^{\frac{s+2}{s+1}})$ edges, then G $G$ contains an induced complete bipartite graph on n−o(n) $n-o(n)$ vertices. We also construct graphs to show that the magnitude in o(ns+2s+1) $o({n}^{\frac{s+2}{s+1}})$ is best possible, which disproves Gerbner's conjecture for r=2 $r=2$. [ABSTRACT FROM AUTHOR]

In this paper, we generalize the concepts of (perfect) Roman and Italian dominations to (perfect) strong Roman and Roman k -domination for arbitrary positive integer k. These generalizations cover some of previous ones. After some comparison of their domination numbers, as a first study of these concepts, we study the (perfect, strong, perfect strong) Roman k -domination numbers of complete bipartite graphs. [ABSTRACT FROM AUTHOR]

A graph G = (V , E) is said to be word-representable if a word w can be formed using the letters of the alphabet V such that for every pair of vertices x and y , x y ∈ E if and only if x and y alternate in w. Gaetz and Ji have recently introduced the notion of minimum length word-representants for word-representable graphs. They have also determined the minimum possible length of the word-representants for certain classes of graphs, such as trees and cycles. In this paper, we solved two of the three cases and partially solved the remaining case of an open problem presented in Gaetz and Ji (2020) by Gaetz and Ji. This problem asks to classify all 2-word-representable graphs based on the length of their minimum length word-representants. Furthermore, we found a relation between the maximum and minimum number of occurrences of letters in minimum length word-representants and the diameter of the graph. Finally, we gave an upper bound on the minimum possible length of a word-representant of a graph under certain word-representability preserving graph operations such as connecting two graphs by an edge and gluing two graphs in a vertex. [ABSTRACT FROM AUTHOR]