Uncover the latest and most impactful research in Graph Theory. Explore pioneering discoveries, insightful ideas and new methods from leading researchers in the field.
What are the most important events and developments in the recent or not so recent past? Climate change? Pandemics? The internet and mobile communications? Artificial intelligence, globalization, or biodiversity loss? Interestingly, all of these...
For an integer \(k \ge 0\) k ≥ 0 , a connected graph G is defined as a k-cactus graph if each edge \(e \in E(G)\) e ∈ E ( G ) is contained in at most k cycles of G. Let \(\mathscr {G}_n^k\) G n k denote the class of all k-cactus graphs of order n,...
Let G be an edge-colored graph. We use e(G) and c(G) to denote the number of edges and colors of G, respectively. A subgraph H is called rainbow if \(c(H)=e(H)\) c ( H ) = e ( H ) . In this paper, we investigate the existence of rainbow matchings of...
(Im)balance indices can be used to quantify the (im)balance of trees by assigning numerical scores to them. An easy way to generate a new index is to construct a compound index, e.g., a linear combination of established indices. Two of the most...
Let K be a finite r-dimensional simplicial complex on n vertices. Motivated by classical bounds for the largest Laplacian eigenvalue of a graph, we study the largest eigenvalue of the combinatorial $$(r-1)$$ ( r - 1 ) -up Laplacian $$L^{\operatorname...
We derive power counting formulas for ribbon graph amplitudes that were recently independently discovered in two contexts, namely as a generalization of the Kontsevich model, and as corresponding to a matrix model approach to the spectral action....
We determine the thickness of the Cartesian product \(K_{6p+4} \, \square \, P_2\) K 6 p + 4 □ P 2 for \(p \ge 0\) p ≥ 0 and of the Cartesian product \(K_8 \, \square \, P_m\) K 8 □ P m for \(m \ge 1\) m ≥ 1 , where \(K_n\) K n and \(P_m\)...
Prior work offers contradictory guidance on whether normalization mitigates oversmoothing in deep Graph Convolutional Networks. We revisit this question under strict experimental control—vanilla GCN, fully fixed hyperparameters, no architectural...
We prove quasi-multiplicativity for critical level-sets of Gaussian free fields (GFF) on the metric graphs \(\widetilde{\mathbb {Z}}^d\) Z ~ d ( \(d\ge 3\) d ≥ 3 ). Specifically, we study the probability of connecting two general sets located on...
Integrity and domination are two significant parameters in the network analysis. While domination deals with controlling the whole network with certain nodes, integrity examines the network’s resilience or weakness when certain nodes are removed....
In the field of intelligent education, cognitive diagnosis aims to assess students’ cognitive states by analyzing their historical response data, serving as a foundation for supporting downstream tasks such as personalized learning recommendations....
Traditional minimum-cost spanning tree methods for the general edge coverage problem tend to overprotect redundant edges, raising costs and complexity when applied to large networks such as power grids, fiber-optic backbones, and IoT...
Detecting infrared small targets continues to be difficult because of indistinct object contours, intense background interference, and restricted multi-scale feature extraction. To tackle such problems, this work introduces EDGRU, an edge-oriented...
For \(d\ge 1\) d ≥ 1 and \(s\ge 0\) s ≥ 0 a \((d,d+s)\) ( d , d + s ) -graph is a graph whose degrees all lie in the interval \(\{d, d+1, \dots ,d+s\}\) { d , d + 1 , ⋯ , d + s } . For \(r\ge 1\) r ≥ 1 and \(a\ge 0\) a ≥ 0 an \((r,r+a)\)...
With the rapid advancement of large language models (LLMs), classic graph learning tasks have greatly benefited from LLMs, including improved encoding of textual features, more efficient construction of graphs from text, and enhanced reasoning over...
In this paper, we first show that second order operators with sign-changing coefficients on general compact graphs are selfadjoint with a discrete spectrum. We secondly give a necessary and sufficient condition for the invertibility of these...
It is folklore that tree-width is monotone under taking subgraphs (i.e. injective graph homomorphisms) and contractions (certain kinds of surjective graph homomorphisms). However, although tree-width is obviously not monotone under anysurjective...
Parallelizing graph algorithms is challenging due to the inherent irregularityof computation, memory access, and communication. The challenge gets exacerbated as newer and different parallel platforms become popular. A domain expert needs to learn...
Given two graphs G and F, if G contains a copy of F, then the rainbow number of F in G, denoted by rb(G, F), is the minimum positive integer t such that any t-edge-coloring of G contains a rainbow copy of F. Let \(\mathcal {M}_{n}(F)\)...
The n-dimensional hypercube \(Q_n\) Q n is a fundamental interconnection network in parallel computing. In practice, link failures and prescribed connection demands must be accommodated simultaneously. This paper studies the existence of a...
Journal
Graphs and Combinatoricsprimarily publishes original research papers in the field of combinatorial mathematics. The scope of the journal includes,...
Journal
Honorary Founder: Pál Erdõs (1913-1996) COMBINATORICA is an international journal of the J. Bolyai Mathematical Society (Fõ utca 68., 1027 Budapest,...
Journal
The development of algorithms is an integral part of computer science. The increasing complexity and scope of computer applications makes the design...
