Search

In this article, the problem of achieving the minimum backbone connectivity cost while simultaneously maximizing user coverage for 5G millimeter-wave (mmWave)-based networks is considered. Let G = (N , E) be an input graph instance with a set of nodes N (base stations) and a set of edges E. It is assumed that G represents a wireless backbone network. Let M represent a set of users to be covered by G. Note that mmWave technology has been considered in the literature as an important candidate solution for 5G networks due to its low latency. However, there remain some problems to be addressed before using this technology. A serious one is that millimeter waves cannot cover large transmission distances. In this article, the proposed methodology consists of formulating mixed-integer programming models to deal with the problem from a management point of view. Our models allow the determination of which of the nodes of G should be active and connected while simultaneously maximizing the total number of covered users. The models are solved with the CPLEX solver using its branch and cut and automatic Benders decomposition algorithms. For this purpose, symmetric complete and sparse graphs are considered. Using the symmetry concept, it is considered that the distances between base stations and users and between base stations themselves are symmetrical. Finally, an efficient local search meta-heuristic is proposed that allows for finding near-optimal solutions. Our numerical experiments indicate that the problem is hard to solve optimally. Thus, instances with up to 40 nodes and 500 users have been solved to optimality so far. In particular, it is observed that one of the models presents slightly better performance in terms of CPU time. Finally, the heuristic approach allows us to obtain tight solutions with less computational effort when dealing with even larger instances of the problem. [ABSTRACT FROM AUTHOR]

In the binary networked public goods (BNPG for short) game, every player needs to decide if she participates in a public project whose utility is shared equally by the community. We study the problem of deciding if there exists a pure strategy Nash equilibrium (PSNE) in such games. The problem is already known to be NP -complete. This casts doubt on predictive power of PSNE in BNPG games. We provide fine-grained analysis of this problem under the lens of parameterized complexity theory. We consider various natural graph parameters and show W [ 1 ] -hardness, XP, and FPT results. Hence, our work significantly improves our understanding of BNPG games where PSNE serves as a reliable solution concept. We finally prove that some graph classes, for example path, cycle, bi-clique, and complete graph, always have a PSNE if the utility function of the players are same. [ABSTRACT FROM AUTHOR]

The index of a signed graph is the largest eigenvalue of its adjacency matrix. Let Un,k,4 be the set of all signed complete graphs of order n whose negative edges induce a unicyclic graph of order k and girth at least 4. In this paper, we identify the signed graphs achieving the maximum index in the class Un,k,4. [ABSTRACT FROM AUTHOR]

We say a class C of graphs is clean if for every positive integer t there exists a positive integer w (t) such that every graph in C with treewidth more than w (t) contains an induced subgraph isomorphic to one of the following: the complete graph K t , the complete bipartite graph K t , t , a subdivision of the (t × t) -wall or the line graph of a subdivision of the (t × t) -wall. In this paper, we adapt a method due to Lozin and Razgon (building on earlier ideas of Weißauer) to prove that the class of all H-free graphs (that is, graphs with no induced subgraph isomorphic to a fixed graph H) is clean if and only if H is a forest whose components are subdivided stars. Their method is readily applied to yield the above characterization. However, our main result is much stronger: for every forest H as above, we show that forbidding certain connected graphs containing H as an induced subgraph (rather than H itself) is enough to obtain a clean class of graphs. Along the proof of the latter strengthening, we build on a result of Davies and produce, for every positive integer η , a complete description of unavoidable connected induced subgraphs of a connected graph G containing η vertices from a suitably large given set of vertices in G. This is of independent interest, and will be used in subsequent papers in this series. [ABSTRACT FROM AUTHOR]

The Gyárfás-Sumner conjecture says that for every forest H and every integer k , if G is H -free and does not contain a clique on k vertices then it has bounded chromatic number. (A graph is H-free if it does not contain an induced copy of H.) Kierstead and Penrice proved it for trees of radius at most two, but otherwise the conjecture is known only for a few simple types of forest. More is known if we exclude a complete bipartite subgraph instead of a clique: Rödl showed that, for every forest H , if G is H -free and does not contain K t , t as a subgraph then it has bounded chromatic number. In an earlier paper with Sophie Spirkl, we strengthened Rödl's result, showing that for every forest H , the bound on chromatic number can be taken to be polynomial in t. In this paper, we prove a related strengthening of the Kierstead-Penrice theorem, showing that for every tree H of radius two and integer d ≥ 2 , if G is H -free and does not contain as a subgraph the complete d -partite graph with parts of cardinality t , then its chromatic number is at most polynomial in t. [ABSTRACT FROM AUTHOR]

A block graph is a graph in which every block is a complete graph. Denote by K n , q the set of block graphs with n vertices and all blocks on q + 1 vertices for every q ≥ 2. Recently, Zhao and Liu (2023) determined the minimum spectral radius of graphs in K n , q , which verified a conjecture posed by Conde et al. (2022). Replacing the complete graph by a general block or a cycle, we define a generalized block graph or a cycle tree, respectively. Let B n , q (resp. C n , q) be the set of generalized block graphs (resp. cycle trees) on n vertices and in which each block is of order q + 1 for q ≥ 2. In this paper, we obtain the maximum/minimum spectral radius of a graph in C n , q. Furthermore, we determine the extremal graph attaining the minimum spectral radius among graphs in B n , q , which coincides with that in C n , q. [ABSTRACT FROM AUTHOR]

The energy of a simple graph G of order n , denoted by E (G) , is E (G) = | λ 1 | + ⋯ + | λ n | , where λ 1 , ... , λ n are the eigenvalues of G. Recently, it has been conjectured that if all eigenvalues of G are non-zero, then E (G) ≥ Δ (G) + δ (G) and the equality holds if and only if G is a complete graph, where δ (G) and Δ (G) are the minimum degree and the maximum degree of vertices of G , respectively. Motivated by this conjecture we find some results for energy of graphs in terms of the number of vertices, the number of edges and the nullity. We prove that if G is a graph with n vertices and m edges such that G has no eigenvalue in the interval (− 1 , 1) , then E (G) ≥ n − 1 + 2 m − n + 1 and the equality holds if and only if G is a disjoint union of some special complete graphs. In particular, we prove that the above conjecture is true for graphs that have no eigenvalue in the interval (− 1 , 1). [ABSTRACT FROM AUTHOR]

We present new sharp sufficient conditions for the existence of properly colored and rainbow C4 ${C}_{4}$'s in edge‐colored graphs. Our first results deal with sharp color neighborhood conditions for the existence of properly colored C4 ${C}_{4}$'s in edge‐colored complete graphs and complete bipartite graphs, respectively. Next, we characterize the extremal graphs for an anti‐Ramsey number result due to Alon on the existence of rainbow C4 ${C}_{4}$'s in edge‐colored complete graphs. We also generalize Alon's result from complete to general edge‐colored graphs. Finally, we derive a structural property regarding the extremal graphs for a bipartite counterpart of Alon's result due to Axenovich, Jiang, and Kündgen on the existence of rainbow C4 ${C}_{4}$'s in edge‐colored complete bipartite graphs. We also generalize their result from complete to general bipartite edge‐colored graphs. [ABSTRACT FROM AUTHOR]

The crossing number of a graph G , denoted by cr (G) , is defined to be the minimum number of crossings that arise among all its drawings in the plane. This concept has been of interest to many researchers who have studied it for many families of graphs. In this paper, we introduce the crossing number of Cartesian product of sunlet graph S m with path P n . Further, we prove that the crossing number of S m □ P 2 is equal to m , along with giving a conjecture for the general case. In addition, we utilize the vertex's rotation concept in order to prove some necessary conditions for the complete bipartite graph K m , n to be optimal when it is drawn in the plane, by presenting an upper bound for the crossing number of any subgraph in it together with determining the exact number of crossings in case the vertices of subgraph have the same rotation. [ABSTRACT FROM AUTHOR]

Let P be a set of n ≥ 1 points in general position in R 2. The edge disjointness graph D (P) of P is the graph whose vertices are all the segments with endpoints in P , two of which are adjacent in D (P) if and only if they are disjoint. In this note, we give a full characterization of all those edge disjointness graphs that are hamiltonian. More precisely, we shall show that there are exactly 9 order types of P for which D (P) is not hamiltonian. Additionally, from one of these 9 order types, we derive a counterexample to a criterion for the existence of hamiltonian cycles due to A. D. Plotnikov in 1998. [ABSTRACT FROM AUTHOR]

In this paper, first, we explain the concept of magic graphs, and then we describe the complete magic labeling of the vertices of a graph. Also, some conditions that must be met so that this labeling can be done in complete bipartite graphs are stated. [ABSTRACT FROM AUTHOR]

Stabbing Planes (also known as Branch and Cut) is a proof system introduced very recently which, informally speaking, extends the DPLL method by branching on integer linear inequalities instead of single variables. The techniques known so far to prove size and depth lower bounds for Stabbing Planes are generalizations of those used for the Cutting Planes proof system. For size lower bounds these are established by monotone circuit arguments, while for depth these are found via communication complexity and protection. As such these bounds apply for lifted versions of combinatorial statements. Rank lower bounds for Cutting Planes are also obtained by geometric arguments called protection lemmas. In this work we introduce two new geometric approaches to prove size/depth lower bounds in Stabbing Planes working for any formula: (1) the antichain method, relying on Sperner's Theorem and (2) the covering method which uses results on essential coverings of the boolean cube by linear polynomials, which in turn relies on Alon's combinatorial Nullenstellensatz. We demonstrate their use on classes of combinatorial principles such as the Pigeonhole principle, the Tseitin contradictions and the Linear Ordering Principle. By the first method we prove almost linear size lower bounds and optimal logarithmic depth lower bounds for the Pigeonhole principle and analogous lower bounds for the Tseitin contradictions over the complete graph and for the Linear Ordering Principle. By the covering method we obtain a superlinear size lower bound and a logarithmic depth lower bound for Stabbing Planes proof of Tseitin contradictions over a grid graph. [ABSTRACT FROM AUTHOR]

An edge irregular total k-labeling of a graph G is a labeling of the vertices and edges of G with labels from the set {1, 2, ..., k} in such a way that any two different edges have distinct weights. The weight of an edge uv is the sum of the label of uv and the labels of vertices u and v. The minimum k for which the graph G has an edge irregular total k-labeling is called the total edge irregularity strength of G. In this paper, we determine the exact value of the total edge irregularity strength of Pn + Km. [ABSTRACT FROM AUTHOR]

All the graphs considered in this article are simple and undirected. Let G = (V(G),E(G)) be a simple undirected Graph. A function f∶ V(G)→{1,2} is called Harmonic Mean Cordial if the induced function f* ∶ E(G) → {1,2} defined by f* (uv... satisfies the condition | vf (i)- vf (j)|≤ 1 and | ef (i)- ef (j)|≤ 1 for any i, j∈ {1,2}, where vf (x) and ef (x) denotes the number of vertices and number of edges with label x respectively and [x] denotes the greatest integer less than or equals to x. A Graph G is called Harmonic Mean Cordial graph if it admits Harmonic Mean Cordial labeling. In this article, we have provided some graphs which are not Harmonic Mean Cordial and also we have provided some graphs which are Harmonic Mean Cordial. [ABSTRACT FROM AUTHOR]

A Latin square is a matrix of symbols such that each symbol occurs exactly once in each row and column. A Latin square L$L$ is row‐Hamiltonian if the permutation induced by each pair of distinct rows of L$L$ is a full cycle permutation. Row‐Hamiltonian Latin squares are equivalent to perfect 1‐factorisations of complete bipartite graphs. For the first time, we exhibit a family of Latin squares that are row‐Hamiltonian and also achieve precisely one of the related properties of being column‐Hamiltonian or symbol‐Hamiltonian. This family allows us to construct non‐trivial, anti‐associative, isotopically L$L$‐closed loop varieties, solving an open problem posed by Falconer in 1970. [ABSTRACT FROM AUTHOR]

Whatever malware protection is upcoming, still the data are prone to cyber-attacks. The most threatening Structured Query Language Injection Attack (SQLIA) happens at the database layer of web applications leading to unlimited and unauthorized access to confidential information through malicious code injection. Since feature extraction accuracy significantly influences detection results, extracting the features of a query that predominantly contributes to SQL Injection (SQLI) is the most challenging task for the researchers. So, the proposed work primarily focuses on that using modified parse-tree representation. Some existing techniques used graph representation to identify characteristics of the query based on a predefined fixed list of SQL keywords. As the complete graph representation requires high time complexity for traversals due to the unnecessary links, a modified parse tree of tokens is proposed here with restricted links between operators (internal nodes) and operands (leaf nodes) of the WHERE clause. Tree siblings from the leaf nodes comprise the WHERE clause operands, where the attackers try to manipulate the conditions to be true for all the cases. A novelty of this work is identifying patterns of legitimate and injected queries from the proposed modified parse tree and applying a pattern-based neural network (NN) model for detecting attacks. The proposed approach is applied in various machine learning (ML) models and a neural network model, Multi-Layer Perceptron (MLP). With the scrupulously extracted patterns and their importance (weights) in legitimate and injected queries, the MLP model provides better results in terms of accuracy (97.85%), precision (93.8%), F1-Score (96%), and AUC (97.8%). [ABSTRACT FROM AUTHOR]

Let G⃗ = (V, A) be an oriented graph and G the underlying graph of G⃗. An orientedk-coloring of G⃗ is a partition of V into k color classes, such that there is no pair of adjacent vertices belonging to the same class and all the arcs between a pair of color classes have the same orientation. The smallest k such that G⃗ admits an oriented k-coloring is the oriented chromatic numberχo(G⃗) = k of G⃗. The oriented chromatic numberχo(G) of the undirected graph G is the maximum of χo(G⃗) for all orientations G⃗ of G. Oriented chromatic number of the product of two graphs G1, G2 was widely studied, but the disjoint union G1∪G2 has not yet been considered. In this article we proved bounds for the oriented chromatic number of any two oriented graphs and we also proved that given two complete graphs Kn and Km with n≥m, there is a real number α∈ (1, 3) such that χo(Kn∪Km) = n + m−α log2(m). Additionally, we established exact values of the union of one complete graph with one cycle and of one complete graph with a forest. [ABSTRACT FROM AUTHOR]

A graceful labeling of a graph G with m edges consists in labeling the vertices of G with distinct integers from 0 to m such that each edge is uniquely identified by the absolute difference of the labels of its endpoints. In this work, we study the graceful labeling problem in the context of maker-breaker graph games. The Graceful Game was introduced by Tuza, in 2017, as a two-players game on a connected graph in which the players, Alice and Bob, take moves labeling the vertices with distinct integers from 0 to m. Players are constrained to use only legal labelings (moves), that is, after a move, all edge labels are distinct. Alice's goal is to obtain a graceful labeling for the graph, as Bob's goal is to prevent it from happening. In this work, we study winning strategies for Alice and Bob in graph classes: paths, complete graphs, cycles, complete bipartite graphs, caterpillars, trees, gear graphs, web graphs, prisms, hypercubes, 2-powers of paths, wheels and fan graphs. [ABSTRACT FROM AUTHOR]

A multipath in a directed graph is a disjoint union of paths. The multipath complex of a directed graph G${\tt G}$ is the simplicial complex whose faces are the multipaths of G${\tt G}$. We compute Euler characteristics, and associated generating functions, of the multipath complexes of directed graphs from certain families, including transitive tournaments and complete bipartite graphs. We show that if G${\tt G}$ is a linear graph, polygon, small grid or transitive tournament, then the homotopy type of the multipath complex of G${\tt G}$ is always contractible or a wedge of spheres. We introduce a new technique for decomposing directed graphs into dynamical regions, which allows us to simplify the homotopy computations. [ABSTRACT FROM AUTHOR]

The Kronecker cover of a graph G is the Kronecker product of G and K2. The matching book embedding of a graph G is an embedding of G with the vertices on the spine, each edge within a single page so that the edges on each page do not intersect and the degree of vertices on each page is at most one. The matching book thickness of G is the minimum number of pages in a matching book embeddding of G and it denoted by mbt(G). A graph G is dispersable if mbt(G) = Δ(G), nearly dispersable if mbt(G) = Δ(G)+1. In this paper, the dispersability of the Kronecker cover of the Cartesian product of complete graphs Kp and cycles Cq is determined. [ABSTRACT FROM AUTHOR]

We solve the open problem posed in Modular irregularity strength of graphs, Electron. J. Graph Theory and Appl. 8 (2020), 435-433, asking about the modular irregularity strength of the complete graph Kn for all n ≥ 3. Furthermore, we establish also the exact values of the modular irregularity strength of complete bipartite graphs Kn;n+t for any positive integer n and t = 0, 1, 2. [ABSTRACT FROM AUTHOR]

Purpose: The main objective of this study is to conduct a time analysis on a complete PERT network in a situation where all activities in the network are critical. This analysis is more exploratory and theoretical in nature, as it assumes a very specific case of a project and the potential implications arising from it. Design/methodology/approach: The analysis was performed on the full PERT network including 6 events and the resulting number of 15 activities. The numerical procedure was carried out by: determining the number of events and parameters of the project duration, determining the (maximum) number of activities - determining the parameters of the distribution of activity durations using mathematical programming, determining the number of iterations, in each iteration: generating activity durations, determining critical paths, determining time duration of the project and analysis of the results obtained. Findings: The work draws three main conclusions: the distribution of the project duration differs significantly from the theoretical PERT time, the theoretical activity durations affect the critical importance of activities in the project implementation, the number of events in the critical path affects the project implementation deadline. Research limitations/implications: The obtained results depend on the adopted methodology, in particular the numerical procedure for generating times: optimistic, modal, pessimistic of activities and generating activity durations from a normal distribution. Further research will focus on these issues. Originality/value: the main novelty of the work is the analysis using Monte Carlo simulation on the full PERT network, where all activities are critical. [ABSTRACT FROM AUTHOR]

A series-parallel graph is a graph that does not contain a complete graph with four vertices as a minor. A new explicit simpler formula for the number of labeled series-parallel biconnected graphs with a given number of vertices is obtained. [ABSTRACT FROM AUTHOR]

Reinterpretation of the Fermat principle governing the propagation of light in media within the Ramsey theory is suggested. Complete bi-colored graphs corresponding to light propagation in media are considered. The vertices of the graphs correspond to the points in real physical space in which the light sources or sensors are placed. Red links in the graphs correspond to the actual optical paths, emerging from the Fermat principle. A variety of optical events, such as refraction and reflection, may be involved in light propagation. Green links, in turn, denote the trial/virtual optical paths, which actually do not occur. The Ramsey theorem states that within the graph containing six points, inevitably, the actual or virtual optical cycle will be present. The implementation of the Ramsey theorem with regard to light propagation in metamaterials is discussed. The Fermat principle states that in metamaterials, a light ray, in going from point S to point P, must traverse an optical path length L that is stationary with respect to variations of this path. Thus, bi-colored graphs consisting of links corresponding to maxima or minima of the optical paths become possible. The graphs, comprising six vertices, will inevitably demonstrate optical cycles consisting of the mono-colored links corresponding to the maxima or minima of the optical path. The notion of the "inverse graph" is introduced and discussed. The total number of triangles in the "direct" (source) and "inverse" Ramsey optical graphs is the same. The applications of "Ramsey optics" are discussed, and an optical interpretation of the infinite Ramsey theorem is suggested. [ABSTRACT FROM AUTHOR]

The k -token graph F k (G) of a graph G is the graph whose vertices are the k -subsets of vertices from G , two of which being adjacent whenever their symmetric difference is a pair of adjacent vertices in G. It is a known result that the algebraic connectivity (or second Laplacian eigenvalue) of F k (G) equals the algebraic connectivity of G. In this paper, we first give results that relate the algebraic connectivities of a token graph and the same graph after removing a vertex. Then, we prove the result on the algebraic connectivity of 2-token graphs for two infinite families: the odd graphs O r for all r , and the multipartite complete graphs K n 1 , n 2 , ... , n r for all n 1 , n 2 , ... , n r In the case of cycles, we present a new method that allows us to compute the whole spectrum of F 2 (C n). This method also allows us to obtain closed formulas that give asymptotically exact approximations for most of the eigenvalues of F 2 (C n). [ABSTRACT FROM AUTHOR]

This article presents a data-driven approach called Intelligent Team Formation and Player Selection (ITFPS), aimed at assisting football coaches in making informed decisions about team formation and player selection. The proposed approach utilizes deep neural networks to evaluate the suitability of each player for different positions on the field. The problem is then formulated as finding the maximum weighted matching in a complete bipartite graph, with the objective of achieving the best possible alignment between team members and the positions designated by the coach. The Hungarian algorithm is employed to facilitate this matching process. Furthermore, the approach allows coaches to select a system of distinct representatives for each position, based on the specific qualities expected from players in a given match. The effectiveness of the approach is demonstrated through tests conducted on four teams from the 2021–2022 English Premier League. The results indicate that ITFPS produces decisions comparable to those made by successful coaches. By optimizing team formations and enabling the utilization of rotating formations, this approach not only enhances team performance but also empowers coaches to make strategic decisions while fully leveraging the potential of their players. ITFPS serves as an intelligent assistant for coaches, complementing their strategic perspectives. [ABSTRACT FROM AUTHOR]

Static equilibria in noisy multinomial Q-nary choice (Potts) games on graphs are considered. Equations defining expectation (quantal response) equilibria for arbitrary noise distribution and topology of the underlying graph are written. A detailed analysis of Potts game for complete and random graphs is presented. One-parameter solution reflecting restructuring of solution space is analyzed. It is shown that for the Potts game on the complete graph and Gumbel noise this Ansatz leads to the same equilibrium-defining equation as one of the two equilibrium defining equations in the Potts model in statistical physics. A difference in properties of the mean field Potts model and equilibria in the Potts game on complete graphs is commented upon. The equations defining Potts game equilibria for random graphs for the special case of configuration model in the annealed approximation are derived. A one-parameter solution analogous to that in the Potts game on complete graphs is constructed and the corresponding equation for the case of Gumbel noise is derived. [ABSTRACT FROM AUTHOR]

The article focuses on finite, simple, undirected, and non-trivial graphs, particularly exploring graph labeling concepts and their applications. It mentions the introduction of cordial labeling by Cahit, followed by H- and H2-cordial labeling by Freeda S and Chellathurai R.S, and Mean Cordial Labeling by Albert William, Indira Rajasingh, and S Roy.

Let G be a graph. Assume that to each vertex of a set of vertices $S\subseteq V(G)$ a robot is assigned. At each stage one robot can move to a neighbouring vertex. Then S is a mobile general position set of G if there exists a sequence of moves of the robots such that all the vertices of G are visited while maintaining the general position property at all times. The mobile general position number of G is the cardinality of a largest mobile general position set of G. We give bounds on the mobile general position number and determine exact values for certain common classes of graphs, including block graphs, rooted products, unicyclic graphs, Kneser graphs $K(n,2)$ and line graphs of complete graphs. [ABSTRACT FROM AUTHOR]

This study presents the Drone Swarms Routing Problem (DSRP), which consists of identifying the maximum number of victims in post-disaster areas. The post-disaster area is modeled in a complete graph, where each search location is represented by a vertex, and the edges are the shortest paths between destinations, with an associated weight, corresponding to the battery consumption to fly to a location. In addition, in the DSRP addressed here, a set of drones are deployed in a cooperative drone swarms approach to boost the search. In this context, a V-shaped formation is applied with leader replacements, which allows energy saving. We propose a computation model for the DSRP that considers each drone as an agent that selects the next search location to visit through a simple and efficient method, the Drone Swarm Heuristic. In order to evaluate the proposed model, scenarios based on the Beirut port explosion in 2020 are used. Numerical experiments are presented in the offline and online versions of the proposed method. The results from such scenarios showed the efficiency of the proposed approach, attesting not only the coverage capacity of the computational model but also the advantage of adopting the V-shaped formation flight with leader replacements. [ABSTRACT FROM AUTHOR]

Consider the semigroup of random walk on a complete graph, which we call the Potts semigroup. Diaconis and Saloff-Coste (Ann Appl Probab 6(3):695–750, 1996) computed the maximum ratio between the relative entropy and the Dirichlet form, obtaining the constant α 2 in the 2-log-Sobolev inequality (2-LSI). In this paper, we obtain the best possible non-linear inequality relating entropy and the Dirichlet form (i.e., p-NLSI, p ≥ 1 ). As an example, we show α 1 = 1 + 1 + o (1) log q . Furthermore, p-NLSIs allow us to conclude that for q ≥ 3 , distributions that are not a product of identical distributions can have slower speed of convergence to equilibrium, unlike the case q = 2 . By integrating the 1-NLSI we obtain new strong data processing inequalities (SDPI), which in turn allows us to improve results of Mossel and Peres (Ann Appl Probab 13(3):817–844, 2003) on reconstruction thresholds for Potts models on trees. A special case is the problem of reconstructing color of the root of a q-colored tree given knowledge of colors of all the leaves. We show that to have a non-trivial reconstruction probability the branching number of the tree should be at least log q log q - log (q - 1) = (1 - o (1)) q log q. This recovers previous results (of Sly in Commun Math Phys 288(3):943–961, 2009 and Bhatnagar et al. in SIAM J Discrete Math 25(2):809–826, 2011) in (slightly) more generality, but more importantly avoids the need for any coloring-specific arguments. Similarly, we improve the state-of-the-art on the weak recovery threshold for the stochastic block model with q balanced groups, for all q ≥ 3 . To further show the power of our method, we prove optimal non-reconstruction results for a broadcasting on trees model with Gaussian kernels, closing a gap left open by Eldan et al. (Combin Probab Comput 31(6):1048–1069, 2022). These improvements advocate information-theoretic methods as a useful complement to the conventional techniques originating from the statistical physics. [ABSTRACT FROM AUTHOR]

In 1997, Sierpinski graphs, S (n , k) , were obtained by Klavzar and Milutinovic. The graph S (1 , k) represents the complete graph K k and S (n , 3) is known as the graph of the Tower of Hanoi. Through generalizing the notion of a Sierpinski graph, a graph named a generalized Sierpinski graph, denoted by S i e (Λ , t) , already exists in the literature. For every graph, numerous polynomials are being studied, such as chromatic polynomials, matching polynomials, independence polynomials, and the M-polynomial. For every polynomial there is an underlying geometrical object which extracts everything that is hidden in a polynomial of a common framework. Now, we describe the steps by which we complete our task. In the first step, we generate an M-polynomial for a generalized Sierpinski graph S i e (Λ , t) . In the second step, we extract some degree-based indices of a generalized Sierpinski graph S i e (Λ , t) using the M-polynomial generated in step 1. In step 3, we generate the entropy of a generalized Sierpinski graph S i e (Λ , t) by using the Randić index. [ABSTRACT FROM AUTHOR]

In a finite mathematical structure with a given partition, a substructure is said to be gregarious if either it meets each partition class or it shares at most one element with each partition class. In this paper, we considered edge decompositions of graphs and hypergraphs into gregarious subgraphs and subhypergraphs. We mostly dealt with "complete equipartite" graphs and hypergraphs, where the vertex classes have the same size and precisely those edges or hyperedges of a fixed cardinality are present that do not contain more than one element from any class. Some related graph classes generated by product operations were also considered. The generalization to hypergraphs offers a wide open area for further research. [ABSTRACT FROM AUTHOR]

Simple heuristics for (combinatorial) optimization problems often show a remarkable performance in practice. Worst-case analysis often falls short of explaining this performance. Because of this, "beyond worst-case analysis" of algorithms has recently gained a lot of attention, including probabilistic analysis of algorithms. The instances of many (combinatorial) optimization problems are essentially a discrete metric space. Probabilistic analysis for such metric optimization problems has nevertheless mostly been conducted on instances drawn from Euclidean space, which provides a structure that is usually heavily exploited in the analysis. However, most instances from practice are not Euclidean. Little work has been done on metric instances drawn from other, more realistic, distributions. Some initial results have been obtained in recent years, where random shortest path metrics generated from dense graphs (either complete graphs or Erdős–Rényi random graphs) have been used so far. In this paper we extend these findings to sparse graphs, with a focus on sparse graphs with 'fast growing cut sizes', i.e. graphs for which | δ (U) | = Ω (| U | ε) for some constant ε ∈ (0 , 1) for all subsets U of the vertices, where δ (U) is the set of edges connecting U to the remaining vertices. A random shortest path metric is constructed by drawing independent random edge weights for each edge in the graph and setting the distance between every pair of vertices to the length of a shortest path between them with respect to the drawn weights. For such instances generated from a sparse graph with fast growing cut sizes, we prove that the greedy heuristic for the minimum distance maximum matching problem, and the nearest neighbor and insertion heuristics for the traveling salesman problem all achieve a constant expected approximation ratio. Additionally, for instances generated from an arbitrary sparse graph, we show that the 2-opt heuristic for the traveling salesman problem also achieves a constant expected approximation ratio. [ABSTRACT FROM AUTHOR]

Let H and M be two connected subgraphs of an interconnection network G. If the removal of any minimum H-structure-cut (respectively, minimum H-substructure-cut) splits G into exactly two components, one of which is isomorphic to M, then G is said to be hyper H | M -connected (respectively, hyper sub- H | M -connected). The hierarchical star network H S n is one of alternative interconnection networks for multiprocessor systems. Let n ≥ 4 , 1 ≤ t ≤ n − 2 and 2 ≤ r ≤ n − 2. In this paper, we prove that (i) both the K 1 , 1 -structure connectivity and the sub- K 1 , 1 -structure connectivity of H S n are n; and (ii) both the K 1 , r -structure connectivity and the sub- K 1 , r -structure connectivity of H S n are n − 1 ; and (iii) H S n is hyper K 1 , t | K 1 -connected and hyper sub- K 1 , t | K 1 -connected, where K 1 is the complete graph with one vertex and K 1 , t is a star with 1 + t vertices. [ABSTRACT FROM AUTHOR]

The token graphs of graphs have been studied at least from the 80’s with different names and by different authors. The Johnson graph J(n, k) is isomorphic to the k-token graph of the complete graph Kn. To our knowledge, the unique results about the automorphism groups of token graphs are for the case of the Johnson graphs. In this paper we begin the study of the automorphism groups of token graphs of another graphs. In particular we obtain the automorphism group of the k-token graph of the path graph Pn, for n 6= 2k. Also, we obtain the automorphism group of the 2-token graph of the following graphs: cycle, star, fan and wheel graphs. [ABSTRACT FROM AUTHOR]

We study a graph-based generalization of the Galam opinion formation model. Consider a simple connected graph which represents a social network. Each node in the graph is colored either blue or white, which indicates a positive or negative opinion on a new product or a topic. In each discrete-time round, all nodes are assigned randomly to groups of different sizes, where the node(s) in each group form a clique in the underlying graph. All the nodes simultaneously update their color to the majority color in their group. If there is a tie, each node in the group chooses one of the two colors uniformly at random. Investigating the convergence time of the model, our experiments show that the convergence time is a logarithm function of the number of nodes for a complete graph and a quadratic function for a cycle graph. We also study the various strategies for selecting a set of seed nodes to maximize the final cascade of one of the two colors, motivated by viral marketing. We consider the algorithms where the seed nodes are selected based on the graph structure (nodes' centrality measures such as degree, betweenness, and closeness) and the individual's characteristics (activeness and stubbornness). We provide a comparison of such strategies by conducting experiments on different real-world and synthetic networks. [ABSTRACT FROM AUTHOR]

Ahanjideh, Akbari, Fakharan and Trevisan proposed a conjecture on the distribution of the Laplacian eigenvalues of graphs: for any connected graph of order n with diameter d ≥ 2 that is not a path, the number of Laplacian eigenvalues in the interval [ n − d + 2 , n ] is at most n − d. We show that the conjecture is true, and give a complete characterization of graphs for which the conjectured bound is attained. This establishes an interesting relation between the spectral and classical parameters. [ABSTRACT FROM AUTHOR]

Let G $G$ be a simple graph and λ(G) $\lambda (G)$ the spectral radius of G $G$. For k≥2 $k\ge 2$, a k $k$‐edge decomposition (H1,...,Hk) $({H}_{1},{\rm{\ldots }},{H}_{k})$ is k $k$ spanning subgraphs such that their edge sets form a k $k$‐partition of the edge set of G $G$. In this paper, we obtain some sharp lower and upper bounds for λ(H1)+⋯+λ(Hk) $\lambda ({H}_{1})+\,\cdots \,+\lambda ({H}_{k})$ in terms of the clique number of Hi ${H}_{i}$ and the size of G $G$, and discuss what k $k$‐edge decomposition (H1,...,Hk) $({H}_{1},{\rm{\ldots }},{H}_{k})$ can maximize λ(H1)+⋯+λ(Hk) $\lambda ({H}_{1})+\cdots \,+\lambda ({H}_{k})$ when G $G$ is a complete graph. These generalize some Nordhaus–Gaddum‐type results on spectral radius for k=2 $k=2$, due to Nosal, Hong and Shu, and Nikiforov. [ABSTRACT FROM AUTHOR]

A spanning tree of a graph with no vertex of degree 2 is called a homeomorphically irreducible spanning tree (HIST) of the graph. In 1990, Albertson, Berman, Hutchinson, and Thomassen conjectured that every twin‐free graph with diameter 2 contains a HIST. Recently, Ando disproved this conjecture and characterized twin‐free graphs with diameter 2 that do contain a HIST. In this paper, we give a complete characterization of all graphs of diameter 2 that contain a HIST. This characterization gives alternative proofs for several known results. [ABSTRACT FROM AUTHOR]

It was conjectured by Ohba, and proved by Noel, Reed and Wu that k $k$‐chromatic graphs G $G$ with ∣V(G)∣≤2k+1 $| V(G)| \le 2k+1$ are chromatic‐choosable. This upper bound on ∣V(G)∣ $| V(G)| $ is tight: if k $k$ is even, then K3⋆(k∕2+1),1⋆(k∕2−1) ${K}_{3\star (k\unicode{x02215}2+1),1\star (k\unicode{x02215}2-1)}$ and K4,2⋆(k−1) ${K}_{4,2\star (k-1)}$ are k $k$‐chromatic graphs with 2k+2 $2k+2$ vertices that are not chromatic‐choosable. It was proved by Zhu and Zhu that these are the only non‐k $k$‐choosable complete k $k$‐partite graphs with 2k+2 $2k+2$ vertices. For G∈{K3⋆(k∕2+1),1⋆(k∕2−1),K4,2⋆(k−1)} $G\in \{{K}_{3\star (k\unicode{x02215}2+1),1\star (k\unicode{x02215}2-1)},{K}_{4,2\star (k-1)}\}$, a bad list assignment of G $G$ is a k $k$‐list assignment L $L$ of G $G$ such that G $G$ is not L $L$‐colourable. Bad list assignments for G=K4,2⋆(k−1) $G={K}_{4,2\star (k-1)}$ were characterized by Enomoto, Ohba, Ota and Sakamoto. In this paper, we first give a simpler proof of this result, and then we characterize bad list assignments for G=K3⋆(k∕2+1),1⋆(k∕2−1) $G={K}_{3\star (k\unicode{x02215}2+1),1\star (k\unicode{x02215}2-1)}$. Using these results, we characterize all non‐k $k$‐choosable k $k$‐chromatic graphs with 2k+2 $2k+2$ vertices. [ABSTRACT FROM AUTHOR]

Hypergraph Lagrangian function has been a helpful tool in several celebrated results in extremal combinatorics. Let G be an r-uniform graph on [n] and let x = (x 1 , ... , x n) ∈ [ 0 , ∞) n. The graph Lagrangian function is defined to be λ (G , x) = ∑ e ∈ E (G) ∏ i ∈ e x i. The graph Lagrangian is defined as λ (G) = max { λ (G , x) : x ∈ Δ } , where Δ = { x = (x 1 , x 2 , ... , x n) ∈ [ 0 , 1 ] n : x 1 + x 2 + ⋯ + x n = 1 }. The Lagrangian density π λ (F) of an r-graph F is defined to be π λ (F) = sup { r ! λ (G) : G does not contain F }. Sidorenko (Combinatorica 9:207–215, 1989) showed that the Lagrangian density of an r-uniform hypergraph F is the same as the Turán density of the extension of F. Therefore, determining the Lagrangian density of a hypergraph will add a result to the very few known results on Turán densities of hypergraphs. For an r-uniform graph H with t vertices, π λ (H) ≥ r ! λ (K t - 1 r) since K t - 1 r (the complete r-uniform graph with t - 1 vertices) does not contain a copy of H. We say that an r-uniform hypergraph H with t vertices is λ -perfect if the equality π λ (H) = r ! λ (K t - 1 r) holds. A fundamental theorem of Motzkin and Straus implies that all 2-uniform graphs are λ -perfect. It is interesting to understand the λ -perfect property for r ≥ 3. Our first result is to show that the disjoint union of a λ -perfect 3-graph and S 2 , t = { 123 , 124 , 125 , 126 , ... , 12 (t + 2) } is λ -perfect, this result implies several previous results: Taking H to be the 3-graph spanned by one edge and t = 1 , we obtain the result by Hefetz and Keevash (J Comb Theory Ser A 120:2020–2038, 2013) that a 3-uniform matching of size 2 is λ -perfect. Doing it repeatedly, we obtain the result in Jiang et al. (Eur J Comb 73:20–36, 2018) that any 3-uniform matching is λ -perfect. Taking H to be the 3-uniform linear path of length 2 or 3 and t = 1 repeatedly, we obtain the results in Hu et al. (J Comb Des 28:207–223, 2020). Earlier results indicate that K 4 3 - = { 123 , 124 , 134 } and F 5 = { 123 , 124 , 345 } are not λ -perfect, we show that the disjoint union of K 4 3 - (or F 5 ) and S 2 , t are λ -perfect. Furthermore, we show the disjoint union of a 3-uniform hypergraph H and S 2 , t is λ -perfect if t is large. We also give an irrational Lagrangian density of a family of four 3-uniform hypergraphs. [ABSTRACT FROM AUTHOR]

The k -edge-colored bipartite Gallai–Ramsey number bgr k (G : H) is defined as the minimum integer n such that n 2 ≥ k and for every N ≥ n , every edge-coloring (using all k colors) of complete bipartite graph K N , N contains a rainbow copy of G or a monochromatic copy of H. In this paper, we first study the structural theorem on the complete bipartite graph K n , n with no rainbow copy of K 1 , 3. Next, we utilize the results to prove the exact values of bgr k (P 4 : H) , bgr k (P 5 : H) , bgr k (K 1 , 3 : H) , where H is a various union of cycles and paths and stars. [ABSTRACT FROM AUTHOR]