检索结果-内蒙古大学图书馆

A complete characterization of magic constants arising from distance magic graphs

学校读者我要写书评

暂无评论

Journal of Combinatorial Mathematics and Combinatorial Computing 2024年 123卷 287-302页

作者： Pawar, Ravindra Singh, Tarkeshwar Mukherjee, Himadri Bagga, Jay Department of Mathematics BITS Pilani K K Birla Goa Campus Goa India Department of Computer Science Ball State University IN United States

A positive integer k is called a magic constant if there is a graph G along with a bijective function f from V (G) to rst |V (G)| natural numbers such that the weight of the vertex w(v) = Puv∈E f(u) = k for all v ∈ V . It is known that all odd positive integers greater than or equal to 3 and the integer powers of 2, 2t, t ≥ 6 are magic constants. In this paper, we characterize all positive integers that are magic constants and generate all distance magic graphs, up to isomorphism, of order up to 10. © 2024 The Author(s).

关键词： graph algorithms

Spectral radius and rainbow k-factors of graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Zhang, Liwen Zhang, Zhiyuan Center for Combinatorics and LPMC Nankai University Tianjin300071 China

Let (formula presented) be a set of graphs on the same vertex set V = {1,...,n} where k · n is even. We say G admits a rainbow k-factor if there exists a k-regular graph F on the vertex set V such that all edges of F are from different members of G . Guo, Lu, Ma, and Ma [Spectral radius and rainbow matchings of graphs, Linear Algebra Appl., 2023] showed a sufficient spectral condition for the existence of a rainbow 1-factor. In this paper, we extend this result to all k-factors for k ≥ 2, which is that if ρ (Gi) ≥ ρ (Kk−1 ∨ (K1 ∪ Kn−k)) for each Gi ∈ G, then G admits a rainbow k-factor unless © 2025, CC BY-NC-ND.

关键词： graph algorithms

Vertex-Colouring of Some 3-Chromatic Circulant graphs $C_N(A,B,C)$ Where $3|\Gcd(N,A)$

学校读者我要写书评

暂无评论

SSRN

SSRN 2025年

作者： Nicoloso, Sara IASI CNR Via dei Taurini 19 Roma00185 Italy

A circulant graph $C_n(a,b,c)$ is the graph with $n$ vertices $\{v_0, \dots, v_{n-1}\}$ such that each vertex $v_i$ is adjacent to vertices $v_{(i+ a) \bmod n}$, $v_{(i+ b) \bmod n}$, $v_{(i+ c) \bmod n}$. The vertex-colouring problem consists in finding an assignment of colours to the vertices of a given graph in such a way that adjacent vertices receive different colours and the number of colours is minimized. In this paper we approach the problem in a purely combinatorial way based on an array representation of the graph, and propose exact linear time vertex-colouring algorithms for a subclass of the connected 3-chromatic circulant graphs $C_n(a,b,c)$ verifying $3|\gcd(n,a)$. © 2025, The Authors. All rights reserved.

关键词： graph algorithms

An Almost Quadratic Vertex Kernel for Subset Feedback Arc Set in Tournaments

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Bai, Tian The University of Hong Kong Hong Kong University of Electronic Science and Technology of China Chengdu China

In the Feedback Arc Set in Tournaments (FAST) problem, we are given a tournament D and a positive integer k, and the objective is to determine whether there exists an arc set S Ď ApDq of size at most k whose removal makes the graph acyclic. This problem is well-known to be equivalent to a natural tournament ranking problem, whose task is to rank players in a tournament such that the number of pairs in which the lower-ranked player defeats the higher-ranked player is no more than k. Using the PTAS for FAST [STOC 2007], Bessy et al. [JCSS 2011] present a p2 ` Εqk-vertex kernel for this problem, given any fixed Ε ą 0. A generalization of FAST, called Subset-FAST, further includes an additional terminal subset T Ď V pDq in the input. The goal of Subset-FAST is to determine whether there is an arc set S Ď ApDq of size at most k whose removal ensures that no directed cycle passes through any terminal in T . Prior to our work, no polynomial kernel for Subset-FAST was known. In our work, we show that Subset-FAST admits an Oppαkq2q-vertex kernel, provided that Subset-FAST has an approximation algorithm with an approximation ratio α. Consequently, based on the known Oplog k log log kq-approximation algorithm, we obtain an almost quadratic kernel for Subset-FAST. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

Motif Counting in Complex Networks: A Comprehensive Survey

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Yin, Haozhe Wang, Kai Zhang, Wenjie He, Yizhang Zhang, Ying Lin, Xuemin The University of New South Wales Australia Antai College of Economics and Management Shanghai Jiao Tong University China Zhejiang Gongshang University China

Motif counting plays a crucial role in understanding the structural properties of networks. By computing motif frequencies, researchers can draw key insights into the structural properties of the underlying network. As networks become increasingly complex, different graph models have been proposed, giving rise to diverse motif patterns. These variations introduce unique computational challenges that require specialized algorithms tailored to specific motifs within different graph structures. This survey provides a comprehensive and structured overview of motif counting techniques across general graphs, heterogeneous graphs, and hypergraphs. We categorize existing algorithms according to their underlying computational strategies, emphasizing key similarities and distinctions. In addition to reviewing current methodologies, we examine their strengths, limitations, and computational trade-offs. Furthermore, we explore future directions in motif counting, including scalable implementations to improve efficiency in large-scale networks, algorithmic adaptations for dynamic, temporal, and attributed graphs, and deeper integration with large language models (LLMs) and graph-based retrieval-augmented generation (graphRAG). By offering a detailed analysis of these approaches, this survey aims to support researchers and practitioners in advancing motif counting for increasingly complex network data. © 2025, CC BY.

关键词： graph algorithms

Interference and Measurement: Obtaining information from the QAOA MaxCut state

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Agarwal, Pranjal Ali, Nada Hillery, Mark Department of Physics and Astronomy Hunter College The City University of New York 695 Park Avenue New YorkNY10065 United States Physics Program Graduate Center The City University of New York 365 Fifth Avenue New YorkNY10016 United States

In using the QAOA algorithm for the MaxCut problem one encodes the number of edges connecting the sets resulting from a partition of the vertices of a graph into phases of amplitudes of a quantum state (QAOA state). One wants to use the quantum state to find partitions with large numbers of edges connecting them. In the QAOA algorithm this is done by using a mixing operation and parameter optimization. Here we want to see what can be done if we only use simple aspects of quantum mechanics, interference and measurement, to extract information from the QAOA state. The idea is to use constructive interference to enhance the amplitudes corresponding to partitions with a large number of edges between the sets. We examine examples, but analytically and numerically. We also show how the results of sequences of measurements can be used to gain information about the landscape of solutions. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

Structural and Combinatorial Properties of 2-Swap Word Permutation graphs

学校读者我要写书评

暂无评论

SSRN

SSRN 2024年

作者： Adamson, Duncan Flaherty, Nathan Potapov, Igor Spirakis, Paul G. Department of Computer Science University of St Andrews North Haugh KY18 9SX United Kingdom Leverhulme Research Centre University of Liverpool 51 Oxford St LiverpoolL7 3NY United Kingdom Department of Computer Science University of Liverpool Ashton Street LiverpoolL69 3BX United Kingdom

In this paper, we study the graph induced by the \emph{$2$-swap} permutation (also known as a transposition) on words with a fixed Parikh vector. Informally, a $2$-swap is a permutation which swaps exactly two symbols in a word, leaving all others unchanged. With these permutations, we define the \emph{Configuration graph}, $G(P)$ for a given Parikh *** vertex in $G(P)$ corresponds to a unique word with the Parikh vector $P$, with an edge between any pair of words $v$ and $w$ if there exists a 2-swap $s$ such that $v \circ s = w$.We provide several key combinatorial properties of this graph, including the exact diameter of this graph, the clique number of the graph, and the relationships between subgraphs within this ***, we show that for every vertex in the graph, there exists a Hamiltonian path starting at this ***, we provide an algorithm enumerating these paths from a given input word of length $n$ with a delay of at most $O(\sigma \log n)$ between outputting edges, requiring $O(n \log n)$ preprocessing. © 2024, The Authors. All rights reserved.

关键词： graph algorithms

algorithms for Distance Problems in Continuous graphs

学校读者我要写书评

暂无评论

arXiv 2025年

作者： Cabello, Sergio Garijo, Delia Kalb, Antonia Klute, Fabian Parada, Irene Silveira, Rodrigo I. Faculty of Mathematics and Physics University of Ljubljana Ljubljana Slovenia Institute of Mathematics Physics and Mechanics Ljubljana Slovenia University of Seville Spain Technical University of Dortmund Germany Universitat Politècnica de Catalunya Spain

We study the problem of computing the diameter and the mean distance of a continuous graph, i.e., a connected graph where all points along the edges, instead of only the vertices, must be taken into account. It is known that for continuous graphs with m edges these values can be computed in roughly O(m2) time. In this paper, we use geometric techniques to obtain subquadratic time algorithms to compute the diameter and the mean distance of a continuous graph for two well-established classes of sparse graphs. We show that the diameter and the mean distance of a continuous graph of treewidth at most k can be computed in O(n logO(k) n) time, where n is the number of vertices in the graph. We also show that computing the diameter and mean distance of a continuous planar graph with n vertices and F faces takes O(nF log n) time. Copyright © 2025, The Authors. All rights reserved.

关键词： graph algorithms

Games on Debruijn graphs and Cycle Means

学校读者我要写书评

暂无评论

SSRN

SSRN 2025年

作者： Drenska, Nadejda Department of Mathematics Louisiana State University United States

deBruijn graphs are widely used in genomics and computer science. In this paper we present a novel approach to finding weights on edges of doubly weighted deBruijn graphs. Given any fixed set of weights on vertices, we use a repeated two-person zero-sum game to find weights on edges so that every cycle on the deBruijn graph has the same average weight, providing explicit formulas. This approach uses minimax optimal strategies of the players. Once the weights on the edges are determined, we observe that they correspond to solving a set of linear equations with as many equations as there are cycles. This is very surprising, because there are many more cycles than unknowns. Moreover we analyze other, related games on graphs. © 2025, The Authors. All rights reserved.

关键词： graph algorithms