Computer Science › Computational Theory and Mathematics

Advanced Graph Theory Research

Works Count: 68436

Wikipedia

Description

This cluster of papers represents advances in graph theory and algorithms, focusing on topics such as parameterized complexity, fixed-parameter algorithms, constraint satisfaction problems, treewidth, kernelization, complexity classification, approximation algorithms, and homomorphism. The papers cover a wide range of algorithmic applications and theoretical developments in the field of graph theory.

Keywords

Graph Theory; Parameterized Complexity; Algorithmic Applications; Fixed-Parameter Algorithms; Constraint Satisfaction Problems; Treewidth; Kernelization; Complexity Classification; Approximation Algorithms; Homomorphism

Introduction to Graph Theory

2010-09-07

Douglas B. West

1. Fundamental Concepts. Definitions and examples. Paths and proofs. Vertex degrees and counting. Degrees and algorithmic proof. 2. Trees and Distance. Basic properties. Spanning trees and enumeration. Optimization and trees. … 1. Fundamental Concepts. Definitions and examples. Paths and proofs. Vertex degrees and counting. Degrees and algorithmic proof. 2. Trees and Distance. Basic properties. Spanning trees and enumeration. Optimization and trees. Eulerian graphs and digraphs. 3. Matchings and Factors. Matchings in bipartite graphs. Applications and algorithms. Matchings in general graphs. 4. Connectivity and Paths. Cuts and connectivity. k-connected graphs. Network flow problems. 5. Graph Coloring. Vertex colorings and upper bounds. Structure of k-chromatic graphs. Enumerative aspects. 6. Edges and Cycles. Line graphs and edge-coloring. Hamiltonian cycles. Complexity. 7. Planar Graphs. Embeddings and Eulers formula. Characterization of planar graphs. Parameters of planarity. 8. Additional Topics. Perfect graphs. Matroids. Ramsey theory. More extremal problems. Random graphs. Eigenvalues of graphs. Glossary of Terms. Glossary of Notation. References. Author Index. Subject Index.

Fundamentals of Domination in Graphs

2013-12-16

Teresa W. Haynes , Stephen T. Hedetniemi , Peter R. Slater

"Provides the first comprehensive treatment of theoretical, algorithmic, and application aspects of domination in graphs-discussing fundamental results and major research accomplishments in an easy-to-understand style. Includes chapters on domination algorithms … "Provides the first comprehensive treatment of theoretical, algorithmic, and application aspects of domination in graphs-discussing fundamental results and major research accomplishments in an easy-to-understand style. Includes chapters on domination algorithms and NP-completeness as well as frameworks for domination."

Invitation to Fixed-Parameter Algorithms

2006-02-02

Rolf Niedermeier

Abstract This book provides an introduction to the concept of fixed-parameter tractability. The corresponding design and analysis of efficient fixed-parameter algorithms for optimally solving combinatorially explosive (NP-hard) discrete problems is … Abstract This book provides an introduction to the concept of fixed-parameter tractability. The corresponding design and analysis of efficient fixed-parameter algorithms for optimally solving combinatorially explosive (NP-hard) discrete problems is a vividly developing field, with a growing list of applications in various contexts such as network analysis or bioinformatics. The book emphasizes algorithmic techniques over computational complexity theory. It is divided into three parts: a broad introduction that provides the general philosophy and motivation; followed by coverage of algorithmic methods developed over the years in fixed-parameter algorithmics forming the core of the book; and a discussion of the essentials of parameterized hardness theory with a focus on W[1]-hardness which parallels NP-hardness, then stating some relations to polynomial-time approximation algorithms, and finishing up with a list of selected case studies to show the wide range of applicability of the presented methodology.

Graphs and Hypergraphs

1973-01-01

C. Berge

Topological Graph Theory

2003-12-29

Tomaž Pisanski , Primož Potočnik , Jianer Chen +6 more

Introduction Voltage Graphs and Covering Spaces Surfaces and Graph Imbeddings Imbedded Voltage Graphs and Current Graphs Map Colorings The Genus of A Group References. Introduction Voltage Graphs and Covering Spaces Surfaces and Graph Imbeddings Imbedded Voltage Graphs and Current Graphs Map Colorings The Genus of A Group References.

Parameterized Complexity Theory

2006-01-01

Jörg Flum , Martin Grohe

Domination in graphs : advanced topics

1998-01-01

Teresa W. Haynes , Stephen T. Hedetniemi , Peter J. Slater

LP-duality, complementarity and generality of graphical subset parameters dominating functions in graphs fractional domination and related parameters majority domination and its generalizations convexity of external domination-related functions of graphs combinatorial … LP-duality, complementarity and generality of graphical subset parameters dominating functions in graphs fractional domination and related parameters majority domination and its generalizations convexity of external domination-related functions of graphs combinatorial problems on chessboards - II domination in cartesian products - Vizing's conjecture algorithms complexity results domination parameters of a graph global domination distance domination in graphs domatic numbers of graphs and their variants - a survey domination-related parameters topics on domination in directed graphs graphs critical with respect to the domination number bondage, insensitivity and reinforcement.

On the shortest spanning subtree of a graph and the traveling salesman problem

1956-02-01

Joseph B. Kruskal

7. A. Kurosh, Ringtheoretische Probleme die mit dem Burnsideschen Problem uber periodische Gruppen in Zussammenhang stehen, Bull. Acad. Sei. URSS, Ser. Math. vol. 5 (1941) pp. 233-240. 8. J. Levitzki, … 7. A. Kurosh, Ringtheoretische Probleme die mit dem Burnsideschen Problem uber periodische Gruppen in Zussammenhang stehen, Bull. Acad. Sei. URSS, Ser. Math. vol. 5 (1941) pp. 233-240. 8. J. Levitzki, On the radical of a general ring, Bull. Amer. Math. Soc. vol. 49 (1943) pp. 462^66. 9. -, On three problems concerning nil rings, Bull. Amer. Math. Soc. vol. 49 (1943) pp. 913-919. 10. -, On the structure of algebraic algebras and related rings, Trans. Amer. Math. Soc. vol. 74 (1953) pp. 384-409.

View PDF Chat

A Set of Measures of Centrality Based on Betweenness

1977-03-01

Linton C. Freeman

A family of new measures of point and graph centrality based on early intuitions of Bavelas (1948) is introduced. These measures define centrality in terms of the degree to which … A family of new measures of point and graph centrality based on early intuitions of Bavelas (1948) is introduced. These measures define centrality in terms of the degree to which a point falls on the shortest path between others and there fore has a potential for control of communication. They may be used to index centrality in any large or small network of symmetrical relations, whether connected or unconnected.

Reducibility Among Combinatorial Problems

2009-11-06

Richard M. Karp

Graph Minors .XIII. The Disjoint Paths Problem

1995-01-01

Neil Robertson , Paul Seymour

The ellipsoid method and its consequences in combinatorial optimization

1981-06-01

Martin Grötschel , László Lovász , Alexander Schrijver

Expander graphs and their applications

2006-08-07

Shlomo Hoory , Nathan Linial , Avi Wigderson

A major consideration we had in writing this survey was to make it accessible to mathematicians as well as to computer scientists, since expander graphs, the protagonists of our story, … A major consideration we had in writing this survey was to make it accessible to mathematicians as well as to computer scientists, since expander graphs, the protagonists of our story, come up in numerous and often surprising contexts in both fields.But, perhaps, we should start with a few words about graphs in general.They are, of course, one of the prime objects of study in Discrete Mathematics.However, graphs are among the most ubiquitous models of both natural and human-made structures.In the natural and social sciences they model relations among species, societies, companies, etc.In computer science, they represent networks of communication, data organization, computational devices as well as the flow of computation, and more.In mathematics, Cayley graphs are useful in Group Theory.Graphs carry a natural metric and are therefore useful in Geometry, and though they are "just" one-dimensional complexes, they are useful in certain parts of Topology, e.g.Knot Theory.In statistical physics, graphs can represent local connections between interacting parts of a system, as well as the dynamics of a physical process on such systems.The study of these models calls, then, for the comprehension of the significant structural properties of the relevant graphs.But are there nontrivial structural properties which are universally important?Expansion of a graph requires that it is simultaneously sparse and highly connected.Expander graphs were first defined by Bassalygo and Pinsker, and their existence first proved by Pinsker in the early '70s.The property of being an expander seems significant in many of these mathematical, computational and physical contexts.It is not surprising that expanders are useful in the design and analysis of communication networks.What is less obvious is that expanders have surprising utility in other computational settings such as in the theory of error correcting codes and the theory of pseudorandomness.In mathematics, we will encounter e.g.their role in the study of metric embeddings, and in particular in work around the Baum-Connes Conjecture.Expansion is closely related to the convergence rates of Markov Chains, and so they play a key role in the study of Monte-Carlo algorithms in statistical mechanics and in a host of practical computational applications.The list of such interesting and fruitful connections goes on and on with so many applications we will not even

View PDF Chat

Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

1976-12-01

Kellogg S. Booth , George S. Lueker

The monadic second-order logic of graphs. I. Recognizable sets of finite graphs

1990-03-01

Bruno Courcelle

View PDF Chat

Graph minors. II. Algorithmic aspects of tree-width

1986-09-01

Neil Robertson , Paul Seymour

Some simplified NP-complete graph problems

1976-02-01

M. R. Garey , David S. Johnson , Larry Stockmeyer

A Separator Theorem for Planar Graphs

1979-04-01

Richard J. Lipton , Robert E. Tarjan

Let G be any n-vertex planar graph. We prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex … Let G be any n-vertex planar graph. We prove that the vertices of G can be partitioned into three sets A, B, C such that no edge joins a vertex in A with a vertex in B, neither A nor B contains more than ${2n / 3}$ vertices, and C contains no more than $2\sqrt 2 \sqrt n $ vertices. We exhibit an algorithm which finds such a partition A, B, C in $O( n )$ time.

Frequency assignment: Theory and applications

1980-01-01

William K. Hale

In this paper we introduce the minimum-order approach to frequency assignment and present a theory which relates this approach to the traditional one. This new approach is potentially more desirable … In this paper we introduce the minimum-order approach to frequency assignment and present a theory which relates this approach to the traditional one. This new approach is potentially more desirable than the traditional one. We model assignment problems as both frequency-distance constrained and frequency constrained optimization problems. The frequency constrained approach should be avoided if distance separation is employed to mitigate interference. A restricted class of graphs, called disk graphs, plays a central role in frequency-distance constrained problems. We introduce two generalizations of chromatic number and show that many frequency assignment problems are equivalent to generalized graph coloring problems. Using these equivalences and recent results concerning the complexity of graph coloring, we classify many frequency assignment problems according to the "execution time efficiency" of algorithms that may be devised for their solution. We discuss applications to important real world problems and identify areas for further work.

A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

1996-12-01

Hans L. Bodlaender

In this paper, we give for constant k a linear-time algorithm that, given a graph $G = (V,E)$, determines whether the treewidth of G is at most k and, if … In this paper, we give for constant k a linear-time algorithm that, given a graph $G = (V,E)$, determines whether the treewidth of G is at most k and, if so, finds a tree-decomposition of G with treewidth at most k. A consequence is that every minor-closed class of graphs that does not contain all planar graphs has a linear-time recognition algorithm. Another consequence is that a similar result holds when we look instead for path-decompositions with pathwidth at most some constant k.

View PDF Chat

Unit disk graphs

1990-12-01

Brent N. Clark , Charles J. Colbourn , David Johnson

Fibonacci heaps and their uses in improved network optimization algorithms

1987-07-01

Michael L. Fredman , Robert E. Tarjan

In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps ), extends the binomial queues proposed by Vuillemin and studied … In this paper we develop a new data structure for implementing heaps (priority queues). Our structure, Fibonacci heaps (abbreviated F-heaps ), extends the binomial queues proposed by Vuillemin and studied further by Brown. F-heaps support arbitrary deletion from an n -item heap in O (log n ) amortized time and all other standard heap operations in O (1) amortized time. Using F-heaps we are able to obtain improved running times for several network optimization algorithms. In particular, we obtain the following worst-case bounds, where n is the number of vertices and m the number of edges in the problem graph: O ( n log n + m ) for the single-source shortest path problem with nonnegative edge lengths, improved from O ( m log ( m/n +2) n ); O ( n 2 log n + nm ) for the all-pairs shortest path problem, improved from O ( nm log ( m/n +2) n ); O ( n 2 log n + nm ) for the assignment problem (weighted bipartite matching), improved from O ( nm log ( m/n +2) n ); O ( mβ ( m, n )) for the minimum spanning tree problem, improved from O ( m log log ( m/n +2) n ); where β ( m, n ) = min { i | log ( i ) n ≤ m/n }. Note that β ( m, n ) ≤ log * n if m ≥ n . Of these results, the improved bound for minimum spanning trees is the most striking, although all the results give asymptotic improvements for graphs of appropriate densities.

View PDF Chat

Complexity of Finding Embeddings in a k-Tree

1987-04-01

Stefan Arnborg , Derek G. Corneil , Andrzej Proskurowski

A k-tree is a graph that can be reduced to the k-complete graph by a sequence of removals of a degree k vertex with completely connected neighbors. We address the … A k-tree is a graph that can be reduced to the k-complete graph by a sequence of removals of a degree k vertex with completely connected neighbors. We address the problem of determining whether a graph is a partial graph of a k-tree. This problem is motivated by the existence of polynomial time algorithms for many combinatorial problems on graphs when the graph is constrained to be a partial k-tree for fixed k. These algorithms have practical applications in areas such as reliability, concurrent broadcasting and evaluation of queries in a relational database system. We determine the complexity status of two problems related to finding the smallest number k such that a given graph is a partial k-tree. First, the corresponding decision problem is NP-complete. Second, for a fixed (predetermined) value of k, we present an algorithm with polynomially bounded (but exponential in k) worst case time complexity. Previously, this problem had only been solved for $k = 1,2,3$.

Algorithmic Aspects of Vertex Elimination on Graphs

1976-06-01

Donald J. Rose , Robert E. Tarjan , George S. Lueker

We consider a graph-theoretic elimination process which is related to performing Gaussian elimination on sparse symmetric positive definite systems of linear equations. We give a new linear-time algorithm to calculate … We consider a graph-theoretic elimination process which is related to performing Gaussian elimination on sparse symmetric positive definite systems of linear equations. We give a new linear-time algorithm to calculate the fill-in produced by any elimination ordering, and we give two new related algorithms for finding orderings with special properties. One algorithm, based on breadth-first search, finds a perfect elimination ordering, if any exists, in $O(n + e)$ time, if the problem graph has n vertices and e edges. An extension of this algorithm finds a minimal (but not necessarily minimum) ordering in $O(ne)$ time. We conjecture that the problem of finding a minimum ordering is NP-complete

Algorithm 457: finding all cliques of an undirected graph

1973-09-01

Coen Bron , Joep Kerbosch

article Free AccessAlgorithm 457: finding all cliques of an undirected graph Authors: Coen Bron Technological Univ. Eindhoven, Eindhoven, The Netherlands Technological Univ. Eindhoven, Eindhoven, The NetherlandsView Profile , Joep Kerbosch … article Free AccessAlgorithm 457: finding all cliques of an undirected graph Authors: Coen Bron Technological Univ. Eindhoven, Eindhoven, The Netherlands Technological Univ. Eindhoven, Eindhoven, The NetherlandsView Profile , Joep Kerbosch Technological Univ. Eindhoven, Eindhoven, The Netherlands Technological Univ. Eindhoven, Eindhoven, The NetherlandsView Profile Authors Info & Claims Communications of the ACMVolume 16Issue 9Sept. 1973 pp 575–577https://doi.org/10.1145/362342.362367Published:01 September 1973Publication History 1,727citation12,013DownloadsMetricsTotal Citations1,727Total Downloads12,013Last 12 Months993Last 6 weeks372 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

View PDF Chat

Introductory Lectures on Convex Optimization

2004-01-01

Yurii Nesterov

Optimization by Simulated Annealing: An Experimental Evaluation; Part I, Graph Partitioning

1989-12-01

David S. Johnson , C. Aragon , Lyle A. McGeoch +1 more

In this and two companion papers, we report on an extended empirical study of the simulated annealing approach to combinatorial optimization proposed by S. Kirkpatrick et al. That study investigated … In this and two companion papers, we report on an extended empirical study of the simulated annealing approach to combinatorial optimization proposed by S. Kirkpatrick et al. That study investigated how best to adapt simulated annealing to particular problems and compared its performance to that of more traditional algorithms. This paper (Part I) discusses annealing and our parameterized generic implementation of it, describes how we adapted this generic algorithm to the graph partitioning problem, and reports how well it compared to standard algorithms like the Kernighan-Lin algorithm. (For sparse random graphs, it tended to outperform Kernighan-Lin as the number of vertices become large, even when its much greater running time was taken into account. It did not perform nearly so well, however, on graphs generated with a built-in geometric structure.) We also discuss how we went about optimizing our implementation, and describe the effects of changing the various annealing parameters or varying the basic annealing algorithm itself.

Finding the k Shortest Paths

1998-01-01

David Eppstein

We give algorithms for finding the k shortest paths (not required to be simple) connecting a pair of vertices in a digraph. Our algorithms output an implicit representation of these … We give algorithms for finding the k shortest paths (not required to be simple) connecting a pair of vertices in a digraph. Our algorithms output an implicit representation of these paths in a digraph with n vertices and m edges, in time O(m + n log n + k). We can also find the k shortest paths from a given source s to each vertex in the graph, in total time O(m + n log n + kn). We describe applications to dynamic programming problems including the knapsack problem, sequence alignment, maximum inscribed polygons, and genealogical relationship discovery.

Complexity and approximation: Combinatorial optimization problems and their approximability properties

2000-07-01

Giorgio Ausiello , Pierluigi Crescenzi , Giorgio Gambosi +3 more

View PDF Chat

An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

1973-12-01

John E. Hopcroft , Richard M. Karp

The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to $(m + … The present paper shows how to construct a maximum matching in a bipartite graph with n vertices and m edges in a number of computation steps proportional to $(m + n)\sqrt n $.Keywordsalgorithmalgorithmic analysisbipartite graphscomputational complexitygraphsmatching

New methods to color the vertices of a graph

1979-04-01

Daniel Brélaz

This paper describes efficient new heuristic methods to color the vertices of a graph which rely upon the comparison of the degrees and structure of a graph. A method is … This paper describes efficient new heuristic methods to color the vertices of a graph which rely upon the comparison of the degrees and structure of a graph. A method is developed which is exact for bipartite graphs and is an important part of heuristic procedures to find maximal cliques in general graphs. Finally an exact method is given which performs better than the Randall-Brown algorithm and is able to color larger graphs, and the new heuristic methods, the classical methods, and the exact method are compared.

View PDF Chat

Algorithmic graph theory and perfect graphs

1980-12-01

M.J. Rijckaert

Maximum matching and a polyhedron with 0,1-vertices

1965-01-01

Jack Edmonds

Jack Edmonds(Dece mbe Jack Edmonds(Dece mbe

Large Networks and Graph Limits

2012-12-12

László Lovász

Recently, it became apparent that a large number of the most interesting structures and phenomena of the world can be described by networks. To develop a mathematical theory of very … Recently, it became apparent that a large number of the most interesting structures and phenomena of the world can be described by networks. To develop a mathematical theory of very large networks is an important challenge. This book describes one recent approach to this theory, the limit theory of graphs, which has emerged over the last decade. The theory has rich connections with other approaches to the study of large networks, such as property testing in computer science and regularity partition in graph theory. It has several applications in extremal graph theory, including the exact formulations and partial answers to very general questions, such as which problems in extremal graph theory are decidable. It also has less obvious connections with other parts of mathematics (classical and non-classical, like probability theory, measure theory, tensor algebras, and semidefinite optimization). This book explains many of these connections, first at an informal level to emphasize the need to apply more advanced mathematical methods, and then gives an exact development of the theory of the algebraic theory of graph homomorphisms and of the analytic theory of graph limits. This is an amazing book: readable, deep, and lively. It sets out this emerging area, makes connections between old classical graph theory and graph limits, and charts the course of the future. --Persi Diaconis, Stanford University This book is a comprehensive study of the active topic of graph limits and an updated account of its present status. It is a beautiful volume written by an outstanding mathematician who is also a great expositor. --Noga Alon, Tel Aviv University, Israel Modern combinatorics is by no means an isolated subject in mathematics, but has many rich and interesting connections to almost every area of mathematics and computer science. The research presented in Lovasz's book exemplifies this phenomenon. This book presents a wonderful opportunity for a student in combinatorics to explore other fields of mathematics, or conversely for experts in other areas of mathematics to become acquainted with some aspects of graph theory. --Terence Tao, University of California, Los Angeles, CA Laszlo Lovasz has written an admirable treatise on the exciting new theory of graph limits and graph homomorphisms, an area of great importance in the study of large networks. It is an authoritative, masterful text that reflects Lovasz's position as the main architect of this rapidly developing theory. The book is a must for combinatorialists, network theorists, and theoretical computer scientists alike. --Bela Bollobas, Cambridge University, UK

Parameterized Complexity

2002-01-01

Michael R. Fellows

An approach to complexity theory which offers a means of analysing algorithms in terms of their tractability. The authors consider the problem in terms of parameterized languages and taking k-slices … An approach to complexity theory which offers a means of analysing algorithms in terms of their tractability. The authors consider the problem in terms of parameterized languages and taking k-slices of the language, thus introducing readers to new classes of algorithms which may be analysed more precisely than was the case until now. The book is as self-contained as possible and includes a great deal of background material. As a result, computer scientists, mathematicians, and graduate students interested in the design and analysis of algorithms will find much of interest.

Graph coloring problems

1995-07-01

Tommy R. Jensen , Bjarne Toft

Planar Graphs. Graphs on Higher Surfaces. Degrees. Critical Graphs. The Conjectures of Hadwiger and Hajos. Sparse Graphs. Perfect Graphs. Geometric and Combinatorial Graphs. Algorithms. Constructions. Edge Colorings. Orientations and Flows. … Planar Graphs. Graphs on Higher Surfaces. Degrees. Critical Graphs. The Conjectures of Hadwiger and Hajos. Sparse Graphs. Perfect Graphs. Geometric and Combinatorial Graphs. Algorithms. Constructions. Edge Colorings. Orientations and Flows. Chromatic Polynomials. Hypergraphs. Infinite Chromatic Graphs. Miscellaneous Problems. Indexes.

Paths, Trees, and Flowers

1965-01-01

Jack Edmonds

A graph G for purposes here is a finite set of elements called vertices and a finite set of elements called edges such that each edge meets exactly two vertices, … A graph G for purposes here is a finite set of elements called vertices and a finite set of elements called edges such that each edge meets exactly two vertices, called the end-points of the edge. An edge is said to join its end-points. A matching in G is a subset of its edges such that no two meet the same vertex. We describe an efficient algorithm for finding in a given graph a matching of maximum cardinality. This problem was posed and partly solved by C. Berge; see Sections 3.7 and 3.8.

View PDF Chat

Algebraic Graph Theory

2001-01-01

Chris Godsil , Gordon Royle

Graph Theory with Applications

1977-01-01

E. Kay , J. A. Bondy , U. S. R. Murty

View PDF Chat

Subprime and superprime graphs

2025-06-24

Houmem Belkhechine , Cherifa Ben Salha , Rim Romdhane | Discrete Applied Mathematics

On domination polynomials of some graphs

2025-06-24

| Journal of Combinatorial Mathematics and Combinatorial Computing

The article investigates the domination polynomial of generalized friendship graphs. The domination polynomial captures the number of dominating sets of each cardinality in a graph and is known to be … The article investigates the domination polynomial of generalized friendship graphs. The domination polynomial captures the number of dominating sets of each cardinality in a graph and is known to be NP-complete to compute for general graphs. We establish the log-concave and unimodal properties of these polynomials, and determine their peaks. Furthermore, we analyze the distribution of the zeros of aforesaid polynomial and identify their region in the complex plane. Several open problems are proposed for future exploration.

Rainbow and Properly Colored Subgraphs

2025-06-24

Xueliang Li , Jie Hu | Series on concrete and applicable mathematics

Common matching number of a graph

2025-06-23

Magda Dettlaff , Magdalena Lemańska , Jerzy Topp | Discrete Applied Mathematics

Complete Extension and Join of Two Graphs

2025-06-23

T B Athul , Roy John , V. N. Manju +1 more | International Journal of Basic and Applied Sciences

In 2016 [5], Suresh Singh G and Sunitha Grace Zacharia introduced the concept of graph extension by adding edges to G in a particular way. In this paper, we try … In 2016 [5], Suresh Singh G and Sunitha Grace Zacharia introduced the concept of graph extension by adding edges to G in a particular way. In this paper, we try to find out some classes of graphs whose joint is completely extendable.

Perfect triple Roman domination

2025-06-23

M. Kor , Jafar Amjadi , Mustapha Chellali +1 more | Discrete Applied Mathematics

Some Bounds for the Minimum Edge Dominating Energy of Graphs

2025-06-21

| Deleted Journal

An improvement of the bound on the improper odd chromatic number of IC-planar graphs

2025-06-21

Shanshan Zhang , Lianying Miao , Xiaoya Li | Discrete Applied Mathematics

On partitioning a planar graph into two forests of maximum degree at most three

2025-06-20

Jiali Wang , Yan Wang | Discrete Mathematics Algorithms and Applications

Optimal Vertex Set Partitions into Different Closed Neighborhoods in Powers of Graphs and their Complements

2025-06-20

N. Kavitha , Chandru Hegde , K. Karthik | Asian-European Journal of Mathematics

Binding Number Conditions for Path-Factor Uniform Graphs

2025-06-19

Ping Zhang | Bulletin of the Malaysian Mathematical Sciences Society

A Variable Version of the Quasi-Kernel Conjecture

2025-06-19

Jiangdong Ai , Xiangzhou Liu , Fei Peng | The Electronic Journal of Combinatorics

A quasi-kernel of a digraph $D$ is an independent set $Q$ such that every vertex can reach $Q$ in at most two steps. A 48-year conjecture made by P.L. Erdős … A quasi-kernel of a digraph $D$ is an independent set $Q$ such that every vertex can reach $Q$ in at most two steps. A 48-year conjecture made by P.L. Erdős and Székely, known as the small QK conjecture, says that every sink-free digraph contains a quasi-kernel of size at most $n/2$. Recently, Spiro posed the large QK conjecture, that every digraph contains a quasi-kernel $Q$ such that $|N^-[Q]|\geq n/2$, and showed that it follows from the small QK conjecture. In this paper, we establish that the large QK conjecture implies the small QK conjecture with a weaker constant. We also show that the large QK conjecture is equivalent to a sharp version of it, answering affirmatively a question of Spiro. We formulate variable versions of these conjectures, which are still open in general. Not many digraphs are known to have quasi-kernels of size $(1-\alpha)n$ or less. We show that digraphs with bounded dichromatic number have quasi-kernels of size at most $(1-\alpha)n$, by proving a stronger statement.

Points and Lines, Graphs and Networks

2025-06-19

| Cambridge University Press eBooks

Directed Acyclic Graphs

2025-06-18

Dominique Haughton , Jonathan Haughton , Victor S. Y. Lo | Chapman and Hall/CRC eBooks

Arc-disjoint in- and out-branchings in semicomplete split digraphs

2025-06-17

Jiangdong Ai , Yiming Hao , Zhaoxiang Li +1 more | Discrete Applied Mathematics

Spanning Tree Modulus

2025-06-17

Nathan Albin , Pietro Poggi‐Corradini | Chapman and Hall/CRC eBooks

On the Symmetry and Domination Integrity of Some Bidegreed Graphs

2025-06-16

B. Ganesan , R. Sundareswaran | Symmetry

Graphs are one of the dynamic tools used to solve network-related problems and real-time application models. The stability of the network plays a crucial role in ensuring uninterrupted data flow. … Graphs are one of the dynamic tools used to solve network-related problems and real-time application models. The stability of the network plays a crucial role in ensuring uninterrupted data flow. A network becomes vulnerable when a node or a link becomes non-functional. To maintain a stable network connection, it is essential for the nodes to be able to interact with each other. The vulnerability of a network can be defined as the level of resistance it exhibits following the failure of communication links. Graphs serve as vital tools for depicting molecular structures, where atoms are shown as vertices and bonds as edges. The domination number quantifies the least number of atoms (vertices) required to dominate the entire molecular framework. Domination integrity reflects the impact of removing specific atoms on the overall molecular structure. This concept is valuable for forecasting fragmentation and decomposition pathways. In contrast to the domination number, domination integrity evaluates the extent to which the molecule remains intact following the removal of reactive or controlling atoms. It aids in assessing stability, particularly in the contexts of drug design, polymer analysis, or catalytic systems. This work focuses on the vulnerability parameter, specifically examining the domination integrity of a specific group of bidegreed hexagonal chemical network systems such as pyrene PY(p), prolate rectangle Rp,q, honeycomb HC(p), and hexabenzocoronene HBC(p). This work also extends to the calculation of the domination integrity value for Cyclic Silicate CCp and Chain Silicate CSp chemical structure networks.

Some Results on Critical (P5,H)-free Graphs

2025-06-16

Xia Wen , Jorik Jooken , Jan Goedgebeur +1 more | Theoretical Computer Science

View PDF Chat

Rounding Large Independent Sets on Expanders

2025-06-15

Mitali Bafna , Jun-Ting Hsieh , Pravesh K. Kothari

View PDF Chat

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More

2025-06-15

Tuukka Korhonen

View PDF Chat

Subexponential Parameterized Algorithms for Hitting Subgraphs

2025-06-15

Daniel Lokshtanov , Fahad Panolan , Saket Saurabh +2 more

View PDF Chat

Smoothed Analysis for Graph Isomorphism

2025-06-15

Michael Anastos , Matthew Kwan , Benjamin Moore

View PDF Chat

Diverse Beam Search to Find Densest-Known Planar Unit Distance Graphs

2025-06-13

Peter Engel , Owen Hammond-Lee , Yiheng Su +2 more | Experimental Mathematics

The number of nonisomorphic nonorientable 6-gonal embeddings of complete graphs

2025-06-13

Vladimir P. Korzhik | Discrete Applied Mathematics

Proper 3-Dominating Sets in Graphs

2025-06-13

Danmei Chen , Shuangjie Cai | Mathematics

A dominating set is a classic concept that is widely used in road safety, disaster rescue operations, and chemical graphs. In this paper, we introduce a variation of the dominating … A dominating set is a classic concept that is widely used in road safety, disaster rescue operations, and chemical graphs. In this paper, we introduce a variation of the dominating set: the proper 3-dominating set. For a proper 3-dominating set D of graph G, any vertex outside D is adjacent to at least three vertices inside D, and there exists one vertex outside D that is adjacent to three vertices inside D. For graph G, the proper 3-domination number is the minimum cardinality among all proper 3-dominating sets of G. We find that a graph with minimum degree at least 3 or one for which there exists a subgraph with some characteristic always contains a proper 3-dominating set. Further, we find that when certain conditions are met, some graph products, such as the joint product, strong product, lexicographic product, and corona product of two graphs, have a proper 3-dominating set. Moreover, we discover the bounds of the proper 3-domination number. For some special graphs, we get their proper 3-domination numbers.

On Assignment Problem for Heavy Tailed Random Variables

2025-06-13

Mikhail Lifshits , Zhan Shi | Sankhya A

The Zero Forcing Numbers of Peony Graphs and Web Graphs

2025-06-12

Sara Anderton , Kanno Mizozoe , Houston Schuerger +1 more | Deleted Journal

The concept of zero forcing involves a dynamic coloring process by which blue vertices cause white vertices to become blue, with the goal of forcing the entire graph blue while … The concept of zero forcing involves a dynamic coloring process by which blue vertices cause white vertices to become blue, with the goal of forcing the entire graph blue while choosing as few as possible vertices to be initially blue. Past research in this area has focused on structural arguments, with approaches varying from graph substructures to the interplay between local and global graph structures. This paper explores the use of these structural concepts when determining the zero forcing number of complex classes of graphs, specifically two infinite classes of graphs each defined on multiple parameters.

View PDF Chat

Certain Variants of Domatic Partitions of n-Inordinate Invariant Intersection Graphs

2025-06-12

S. Madhumitha , Sudev Naduvath | Asian-European Journal of Mathematics

Generalization of a variant of k-plane trees

2025-06-12

Fidel Ochieng Oduol , Isaac Owino Okoth , Fredrick Oluoch Nyamwala | Deleted Journal

Enumeration of plane trees and noncrossing trees was recently unified by considering d-dimensional plane trees in which ordinary plane trees are 1-dimensional plane trees and noncrossing trees are 2-dimensional … Enumeration of plane trees and noncrossing trees was recently unified by considering d-dimensional plane trees in which ordinary plane trees are 1-dimensional plane trees and noncrossing trees are 2-dimensional plane trees. Also, recently variants of k-plane trees and k-noncrossing trees were introduced and enumerated according to number of nodes, root degree, label of the eldest or youngest child of the root, length of the leftmost path and number of forests with a given number of components. In this paper, we have generalized a variant of k-plane trees and k-noncrossing trees to a d-dimensional version and obtained closed formulas for the trees based on the aforementioned parameters. We have used symbolic method to find the generating functions, obtained the right substitution to solve the generating functions and applied Lagrange-B&uuml;rmann inversion to obtain the formulas. The results of this paper unify known results in the counting of k-plane trees and k-noncrossing trees.

Treewidth Inapproximability and Tight ETH Lower Bound

2024-10-20

Édouard Bonnet

We present a simple, self-contained, linear reduction from 3-SAT to Treewidth. Specifically, it shows that 1.00005-approximating Treewidth is NP-hard, and solving Treewidth exactly requires $2^{\Omega(n)}$ time, unless the Exponential-Time Hypothesis … We present a simple, self-contained, linear reduction from 3-SAT to Treewidth. Specifically, it shows that 1.00005-approximating Treewidth is NP-hard, and solving Treewidth exactly requires $2^{\Omega(n)}$ time, unless the Exponential-Time Hypothesis fails. We further derive, under the latter assumption, that there is some constant $\delta > 1$ such that $\delta$-approximating Treewidth requires time $2^{n^{1-o(1)}}$.

View PDF Chat