32 results on '"Boris Brimkov"'
Search Results
2. On Sets of Line Segments Featuring a Cactus Structure.
- Author
-
Boris Brimkov
- Published
- 2017
- Full Text
- View/download PDF
3. Geometric Approach to Biosequence Analysis.
- Author
-
Boris Brimkov and Valentin E. Brimkov
- Published
- 2014
- Full Text
- View/download PDF
4. Memory Efficient Shortest Path Algorithms for Cactus Graphs.
- Author
-
Boris Brimkov
- Published
- 2013
- Full Text
- View/download PDF
5. A spectral and radial basis function hybrid method for visualizing vascular flows.
- Author
-
Boris Brimkov, Jae-Hun Jung, Jim Kotary, Xinwei Liu, and Jing Zheng
- Published
- 2012
- Full Text
- View/download PDF
6. Minimal Offsets That Guarantee Maximal or Minimal Connectivity of Digital Curves in nD.
- Author
-
Valentin E. Brimkov, Reneta P. Barneva, and Boris Brimkov
- Published
- 2009
- Full Text
- View/download PDF
7. Offset Approach to Defining 3D Digital Lines.
- Author
-
Valentin E. Brimkov, Reneta P. Barneva, Boris Brimkov, and François de Vieilleville
- Published
- 2008
- Full Text
- View/download PDF
8. Intersections and circuits in sets of line segments
- Author
-
Jesse Geneson, Boris Brimkov, Jordan Broussard, Pouria Salehi Nowbandegani, and Alathea Jensen
- Subjects
Control and Optimization ,Computer science ,Applied Mathematics ,Structure (category theory) ,Image processing ,Upper and lower bounds ,Computer Science Applications ,Planar graph ,Combinatorics ,symbols.namesake ,Line segment ,Computational Theory and Mathematics ,Intersection ,Theory of computation ,symbols ,Discrete Mathematics and Combinatorics ,Geometric modeling ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
Sets of straight line segments with special structures and properties appear in various applications of geometric modeling, such as scientific visualization, computer-aided design, and medical image processing. In this paper, we derive sharp upper and lower bounds on the number of intersection points and closed regions that can occur in sets of line segments with certain structure, in terms of the number of segments. In particular, we consider sets of segments whose underlying planar graphs are Halin graphs, cactus graphs, maximal planar graphs, and triangle-free planar graphs, as well as randomly produced segment sets.
- Published
- 2021
9. On the status sequences of trees
- Author
-
Alexander Grigoriev, Boris Brimkov, Aida Abiad, Mathematics, Digital Mathematics, Discrete Mathematics, EAISI Foundational, RS: FSE DACS Mathematics Centre Maastricht, Data Analytics and Digitalisation, RS: GSBE Theme Data-Driven Decision-Making, and QE Operations research
- Subjects
c00 - Mathematical and Quantitative Methods: General ,Technology and Engineering ,General Computer Science ,Existential quantification ,Graph analysis ,Theoretical Computer Science ,Trees ,GRAPHS ,ROBBER ,Combinatorics ,FOS: Mathematics ,Mathematics - Combinatorics ,SPECTRA ,Status injective ,DIMENSION ,Graph algorithms ,Connectivity ,Mathematics ,Status sequence ,Graph partition ,Complexity ,Mathematical and Quantitative Methods: General ,Injective function ,Graph ,Vertex (geometry) ,Mathematics and Statistics ,DISTANCE ,Combinatorics (math.CO) ,Any status ,Tree ,STATUS UNIQUE - Abstract
The status of a vertex $v$ in a connected graph is the sum of the distances from $v$ to all other vertices. The status sequence of a connected graph is the list of the statuses of all the vertices of the graph. In this paper we investigate the status sequences of trees. Particularly, we show that it is NP-complete to decide whether there exists a tree that has a given sequence of integers as its status sequence. We also present some results about trees whose status sequences are comprised of a few distinct numbers or many distinct numbers. In this direction, we provide a partial answer to a conjecture of Shang and Lin from 2011, showing that any status injective tree is unique among trees. Finally, we investigate how orbit partitions and equitable partitions relate to the status sequence.
- Published
- 2021
10. Tangle bases: Revisited
- Author
-
Boris Brimkov and Illya V. Hicks
- Subjects
Combinatorics ,Dynamic programming ,Computer Networks and Communications ,Hardware and Architecture ,Computer science ,Branch-decomposition ,Combinatorial optimization ,Software ,Information Systems ,Tangle - Published
- 2020
11. Computational and Theoretical Challenges for Computing the Minimum Rank of a Graph
- Author
-
Illya V. Hicks, Boris Brimkov, Louis Deaett, Ruth Haas, Derek Mikesell, David Roberson, and Logan Smith
- Subjects
Forts ,General Engineering ,Minimum rank ,Zero forcing ,Maximum nullity ,Matroid - Abstract
The minimum rank of a graph G is the minimum of the ranks of all symmetric adjacency matrices of G. We present a new combinatorial bound for the minimum rank of an arbitrary graph G based on enumerating certain subsets of vertices of G satisfying matroid theoretic properties. We also present some computational and theoretical challenges associated with computing the minimum rank. This includes a conjecture that this bound on the minimum rank actually holds with equality for all graphs. History: This “Challenge” paper was invited by the Editor in Chief and based on the topics raised by the author at his plenary address at the 2022 INFORMS Computing Society Conference in Tampa, Florida. Funding: This work was supported by the National Science Foundation [Grant DMS-1720225]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/ijoc.2022.1219 .
- Published
- 2022
12. Constructions of cospectral graphs with different zero forcing numbers
- Author
-
Aida Abiad, Boris Brimkov, Jane Breen, Thomas R. Cameron, Himanshu Gupta, Ralihe R. Villagran, Combinatorial Optimization 1, and EAISI Foundational
- Subjects
Zero forcing number ,Algebra and Number Theory ,FOS: Mathematics ,Minimum rank ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Maximum nullity ,Graph ,Spectral characterization - Abstract
Several researchers have recently explored various graph parameters that can or cannot be characterized by the spectrum of a matrix associated with a graph. In this paper, we show that several NP-hard zero forcing numbers are not characterized by the spectra of several types of associated matrices with a graph. In particular, we consider standard zero forcing, positive semidefinite zero forcing, and skew zero forcing and provide constructions of infinite families of pairs of cospectral graphs, which have different values for these numbers. We explore several methods for obtaining these cospectral graphs including using graph products, graph joins, and graph switching. Among these, we provide a construction involving regular adjacency cospectral graphs; the regularity of this construction also implies cospectrality with respect to several other matrices including the Laplacian, signless Laplacian, and normalized Laplacian. We also provide a construction where pairs of cospectral graphs can have an arbitrarily large difference between their zero forcing numbers.
- Published
- 2021
13. Power domination throttling
- Author
-
Rutvik Patel, Boris Brimkov, Joshua Carlson, Illya V. Hicks, and Logan A. Smith
- Subjects
Vertex (graph theory) ,05C15, 68Q17 ,General Computer Science ,G.2.1 ,G.2.2 ,0102 computer and information sciences ,02 engineering and technology ,Bandwidth throttling ,01 natural sciences ,Graph ,Theoretical Computer Science ,Combinatorics ,Colored ,010201 computation theory & mathematics ,Bounding overwatch ,Dominating set ,FOS: Mathematics ,0202 electrical engineering, electronic engineering, information engineering ,Mathematics - Combinatorics ,020201 artificial intelligence & image processing ,Combinatorics (math.CO) ,Mathematics - Abstract
A power dominating set of a graph $G=(V,E)$ is a set $S\subset V$ that colors every vertex of $G$ according to the following rules: in the first timestep, every vertex in $N[S]$ becomes colored; in each subsequent timestep, every vertex which is the only non-colored neighbor of some colored vertex becomes colored. The power domination throttling number of $G$ is the minimum sum of the size of a power dominating set $S$ and the number of timesteps it takes $S$ to color the graph. In this paper, we determine the complexity of power domination throttling and give some tools for computing and bounding the power domination throttling number. Some of our results apply to very general variants of throttling and to other aspects of power domination., Comment: 19 pages
- Published
- 2019
14. Improved Computational Approaches and Heuristics for Zero Forcing
- Author
-
Derek Mikesell, Boris Brimkov, and Illya V. Hicks
- Subjects
021103 operations research ,Heuristic ,0211 other engineering and technologies ,General Engineering ,Process (computing) ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Vertex (geometry) ,Combinatorics ,Colored ,010201 computation theory & mathematics ,Graph (abstract data type) ,Graph coloring ,Boolean satisfiability problem ,Heuristics ,Mathematics - Abstract
Zero forcing is a graph coloring process based on the following color change rule: all vertices of a graph [Formula: see text] are initially colored either blue or white; in each timestep, a white vertex turns blue if it is the only white neighbor of some blue vertex. A zero forcing set of [Formula: see text] is a set of blue vertices such that all vertices eventually become blue after iteratively applying the color change rule. The zero forcing number [Formula: see text] is the cardinality of a minimum zero forcing set. In this paper, we propose novel exact algorithms for computing [Formula: see text] based on formulating the zero forcing problem as a two-stage Boolean satisfiability problem. We also propose several heuristics for zero forcing based on iteratively adding blue vertices which color a large part of the remaining white vertices. These heuristics are used to speed up the exact algorithms and can also be of independent interest in approximating [Formula: see text]. Computational results on various types of graphs show that, in many cases, our algorithms offer a significant improvement on the state-of-the-art algorithms for zero forcing. Summary of Contribution: This paper proposes novel algorithms and heuristics for an NP-hard graph coloring problem that has numerous applications. Our exact methods combine Boolean satisfiability modeling with a constraint generation framework commonly used in operations research. The paper also includes an analysis of the facets of the polytope associated with this problem and decomposition techniques which can reduce the size of the problem. Our computational approaches are implemented and tested on a wide variety of graphs and are compared with the state-of-the-art algorithms from the literature. We show that our proposed algorithms based on Boolean satisfiability, in conjunction with the heuristics and order-reduction techniques, yield a significant speedup in some cases.
- Published
- 2021
15. Throttling for the game of Cops and Robbers on graphs
- Author
-
Leslie Hogben, Joshua Carlson, Boris Brimkov, Jane Breen, K. E. Perry, and Carolyn Reinhart
- Subjects
Discrete mathematics ,010102 general mathematics ,0102 computer and information sciences ,Bandwidth throttling ,Positive-definite matrix ,01 natural sciences ,Upper and lower bounds ,Graph ,Theoretical Computer Science ,Combinatorics ,010201 computation theory & mathematics ,Bounding overwatch ,Zero Forcing Equalizer ,Discrete Mathematics and Combinatorics ,Hypercube ,Projective plane ,0101 mathematics ,Mathematics - Abstract
We consider the cop-throttling number of a graph G for the game of Cops and Robbers, which is defined to be the minimum of ( k + capt k ( G ) ) , where k is the number of cops and capt k ( G ) is the minimum number of rounds needed for k cops to capture the robber on G over all possible games. We provide some tools for bounding the cop-throttling number, including showing that the positive semidefinite (PSD) throttling number, a variant of zero forcing throttling, is an upper bound for the cop-throttling number. We also characterize graphs having low cop-throttling number and investigate how large the cop-throttling number can be for a given graph. We consider trees, unicyclic graphs, incidence graphs of finite projective planes (a Meyniel extremal family of graphs), a family of cop-win graphs with maximum capture time, grids, and hypercubes. All the upper bounds on the cop-throttling number we obtain for families of graphs are O ( n ) .
- Published
- 2018
16. Restricted power domination and zero forcing problems
- Author
-
Mary Flagg, Leslie Hogben, Craig Erickson, Boris Brimkov, Daniela Ferrero, and Chassidy Bozeman
- Subjects
Discrete mathematics ,021103 operations research ,Control and Optimization ,Domination analysis ,Applied Mathematics ,0211 other engineering and technologies ,Parallel algorithm ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Computer Science Applications ,Vertex (geometry) ,Treewidth ,Electric power system ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Dominating set ,Bounded function ,Discrete Mathematics and Combinatorics ,Time complexity ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
Power domination in graphs arises from the problem of monitoring an electric power system by placing as few measurement devices in the system as possible. A power dominating set of a graph is a set of vertices that observes every vertex in the graph, following a set of rules for power system monitoring. A practical problem of interest is to determine the minimum number of additional measurement devices needed to monitor a power network when the network is expanded and the existing devices remain in place. In this paper, we study the problem of finding the smallest power dominating set that contains a given set of vertices X. We also study the related problem of finding the smallest zero forcing set that contains a given set of vertices X. The sizes of such sets in a graph G are respectively called the restricted power domination number and restricted zero forcing number of G subject to X. We derive several tight bounds on the restricted power domination and zero forcing numbers of graphs, and relate them to other graph parameters. We also present exact and algorithmic results for computing the restricted power domination number, including integer programs for general graphs and a linear time algorithm for graphs with bounded treewidth. We also use restricted power domination to obtain a parallel algorithm for finding minimum power dominating sets in trees.
- Published
- 2018
17. Spectral bounds for the connectivity of regular graphs with given order
- Author
-
Aida Abiad, Xavier Martínez-Rivera, Suil O, Jingmei Zhang, Boris Brimkov, QE Operations research, and RS: GSBE Theme Data-Driven Decision-Making
- Subjects
010103 numerical & computational mathematics ,0102 computer and information sciences ,01 natural sciences ,Combinatorics ,Indifference graph ,Pathwidth ,Chordal graph ,FOS: Mathematics ,05C50, 05C40 ,Mathematics - Combinatorics ,Edge-connectivity ,Cograph ,0101 mathematics ,Mathematics ,Discrete mathematics ,Algebraic connectivity ,Strongly regular graph ,Algebra and Number Theory ,Regular multigraph ,Mathematics::Spectral Theory ,Vertex-connectivity ,ALGEBRAIC CONNECTIVITY ,NETWORKS ,Second-largest eigenvalue ,Treewidth ,Mathematics and Statistics ,010201 computation theory & mathematics ,TREES ,Maximal independent set ,Combinatorics (math.CO) ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
The second-largest eigenvalue and second-smallest Laplacian eigenvalue of a graph are measures of its connectivity. These eigenvalues can be used to analyze the robustness, resilience, and synchronizability of networks, and are related to connectivity attributes such as the vertex- and edge-connectivity, isoperimetric number, and characteristic path length. In this paper, we present two upper bounds for the second-largest eigenvalues of regular graphs and multigraphs of a given order which guarantee a desired vertex- or edge-connectivity. The given bounds are in terms of the order and degree of the graphs, and hold with equality for infinite families of graphs. These results answer a question of Mohar., 24 pages
- Published
- 2018
18. On the Wiener index, distance cospectrality and transmission regular graphs
- Author
-
Aida Abiad, Boris Brimkov, Lorinda Leshock, Aysel Erey, Xavier Martínez-Rivera, Sung Yell Song, Jason Williford, Suil O, QE Operations research, and RS: GSBE ETBC
- Subjects
FORBIDDEN MINORS ,Diameters ,010103 numerical & computational mathematics ,0102 computer and information sciences ,Wiener index ,01 natural sciences ,Laplacian eigenvalues ,Upper and lower bounds ,Transmission-regular ,Combinatorics ,NUMBER ,VERTICES ,Diameter ,LARGEST EIGENVALUE ,FOS: Mathematics ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,BALANCED GRAPHS ,0101 mathematics ,Algebraic number ,Mathematics ,Distance matrix ,SPECTRUM ,Applied Mathematics ,WIDTH ,Distance cospectral graphs ,Graph ,05C50, 05C12, 94C15 ,010201 computation theory & mathematics ,TREES ,Combinatorics (math.CO) ,Laplacian matrix ,MATRIX ,Distance matrices in phylogeny - Abstract
In this paper, we investigate various algebraic and graph theoretic properties of the distance matrix of a graph. Two graphs are D-cospectral if their distance matrices have the same spectrum. We construct infinite pairs of D-cospectral graphs with different diameter and different Wiener index. A graph is k-transmission-regular if its distance matrix has constant row sum equal to k. We establish tight upper and lower bounds for the row sum of a k-transmission-regular graph in terms of the number of vertices of the graph. Finally, we determine the Wiener index and its complexity for linear k-trees, and obtain a closed form for the Wiener index of block-clique graphs in terms of the Laplacian eigenvalues of the graph. The latter leads to a generalization of a result for trees which was proved independently by Mohar and Merris. (C) 2017 Elsevier B.V. All rights reserved.
- Published
- 2017
19. Injective choosability of subcubic planar graphs with girth 6
- Author
-
Jennifer J. Edmond, Bernard Lidický, Kacy Messerschmidt, Shanise Walker, Boris Brimkov, and Robert Lazar
- Subjects
Discrete mathematics ,05C15, 05C10 ,010102 general mathematics ,G.2.2 ,0102 computer and information sciences ,01 natural sciences ,Injective function ,Graph ,Theoretical Computer Science ,Planar graph ,Combinatorics ,symbols.namesake ,010201 computation theory & mathematics ,Common neighbor ,FOS: Mathematics ,symbols ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Mathematics - Abstract
An injective coloring of a graph $G$ is an assignment of colors to the vertices of $G$ so that any two vertices with a common neighbor have distinct colors. A graph $G$ is injectively $k$-choosable if for any list assignment $L$, where $|L(v)| \geq k$ for all $v \in V(G)$, $G$ has an injective $L$-coloring. Injective colorings have applications in the theory of error-correcting codes and are closely related to other notions of colorability. In this paper, we show that subcubic planar graphs with girth at least 6 are injectively 5-choosable. This strengthens a result of Lu\v{z}ar, \v{S}krekovski, and Tancer that subcubic planar graphs with girth at least 7 are injectively 5-colorable. Our result also improves several other results in particular cases., Comment: 18 pages, 12 figures
- Published
- 2017
20. Complexity and computation of connected zero forcing
- Author
-
Boris Brimkov and Illya V. Hicks
- Subjects
Block graph ,Applied Mathematics ,Computation ,0211 other engineering and technologies ,Unicyclic graphs ,Cactus graph ,021107 urban & regional planning ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Vertex (geometry) ,Combinatorics ,Colored ,010201 computation theory & mathematics ,Zero Forcing Equalizer ,Discrete Mathematics and Combinatorics ,Graph coloring ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
Zero forcing is an iterative graph coloring process whereby a colored vertex with a single uncolored neighbor forces that neighbor to be colored. It is NP-hard to find a minimum zero forcing set – a smallest set of initially colored vertices which forces the entire graph to be colored. We show that the problem remains NP-hard when the initially colored set induces a connected subgraph. We also give structural results about the connected zero forcing sets of a graph related to the graph’s density, separating sets, and certain induced subgraphs. Finally, we give efficient algorithms to find minimum connected zero forcing sets of unicyclic graphs and variants of cactus and block graphs.
- Published
- 2017
21. Integrating Technology-Enhanced Collaborative Surfaces and Gamification for the Next Generation Classroom
- Author
-
Boris Brimkov, Michael Jenkin, Reneta P. Barneva, Kamen Kanev, and Bill Kapralos
- Subjects
Game mechanics ,020205 medical informatics ,Multimedia ,Computer science ,05 social sciences ,Educational technology ,050301 education ,Student engagement ,Collaborative learning ,02 engineering and technology ,Blackboard (design pattern) ,computer.software_genre ,Human–computer interaction ,ComputingMilieux_COMPUTERSANDEDUCATION ,0202 electrical engineering, electronic engineering, information engineering ,Technology integration ,Augmented reality ,0503 education ,computer ,Mobile device - Abstract
We place collaborative student engagement in a nontraditional perspective by considering a novel, more interactive educational environment and explaining how to employ it to enhance student learning. To this end, we explore modern technological classroom enhancements as well as novel pedagogical techniques which facilitate collaborative learning. In our setup, the traditional blackboard or table is replaced by a digitally enabled interactive surface such as a smart board or a tabletop computer. The information displayed on the digital surface can be further enhanced with augmented reality views through mobile apps on student smartphones. We also discuss ways to enhance the instructional process through elements of game mechanics and outline an experimental implementation. Finally, we discuss an application of the proposed technological and pedagogical methods to human anatomy training.
- Published
- 2017
22. Memory efficient algorithms for cactus graphs and block graphs
- Author
-
Illya V. Hicks and Boris Brimkov
- Subjects
Block graph ,Discrete mathematics ,Applied Mathematics ,0102 computer and information sciences ,02 engineering and technology ,01 natural sciences ,Longest path problem ,Treewidth ,Indifference graph ,Pathwidth ,Clique problem ,010201 computation theory & mathematics ,Chordal graph ,020204 information systems ,Partial k-tree ,0202 electrical engineering, electronic engineering, information engineering ,Discrete Mathematics and Combinatorics ,MathematicsofComputing_DISCRETEMATHEMATICS ,Mathematics - Abstract
We present constant-work-space polynomial time algorithms for solving the shortest path problem, finding the chromatic polynomial, clique number, number of components, circumference, and girth of cactus graphs and block graphs. For some of these problems we also present in-place algorithms, which perform faster than the corresponding constant-work-space algorithms. The problems considered are fundamental to many areas of graph theory, computational geometry, and combinatorial optimization, and have a wide range of applications including transportation, robotics, and image processing.
- Published
- 2017
23. Optimizing the trade-off between number of cops and capture time in Cops and Robbers
- Author
-
Anthony Bonato, Jane Breen, Boris Brimkov, Joshua Carlson, Sean English, Jesse Geneson, Leslie Hogben, K. E. Perry, and Carolyn Reinhart
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,05C57, 91A43 ,Computer Science - Discrete Mathematics - Abstract
The cop throttling number $th_c(G)$ of a graph $G$ for the game of Cops and Robbers is the minimum of $k + capt_k(G)$, where $k$ is the number of cops and $capt_k(G)$ is the minimum number of rounds needed for $k$ cops to capture the robber on $G$ over all possible games in which both players play optimally. In this paper, we construct a family of graphs having $th_c(G)= \Omega(n^{2/3})$, establish a sublinear upper bound on the cop throttling number, and show that the cop throttling number of chordal graphs is $O(\sqrt{n})$. We also introduce the product cop throttling number $th_c^{\times}(G)$ as a parameter that minimizes the person-hours used by the cops. This parameter extends the notion of speed-up that has been studied in the context of parallel processing and network decontamination. We establish bounds on the product cop throttling number in terms of the cop throttling number, characterize graphs with low product cop throttling number, and show that for a chordal graph $G$, $th_c^{\times}=1+rad(G)$., Comment: 19 pages, 3 figures
- Published
- 2019
- Full Text
- View/download PDF
24. Graphs that are cospectral for the distance Laplacian
- Author
-
Leslie Hogben, Kate Lorenzen, Mark Yarrow, Carolyn Reinhart, Boris Brimkov, Ken Duna, and Sung-Yell Song
- Subjects
Algebra and Number Theory ,05C500, 05C12, 15A18, 15B57 ,010103 numerical & computational mathematics ,01 natural sciences ,Graph ,Unimodality ,Combinatorics ,Distance matrix ,Diagonal matrix ,FOS: Mathematics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,0101 mathematics ,Laplacian matrix ,Laplace operator ,Circulant matrix ,Mathematics ,Characteristic polynomial - Abstract
The distance matrix $\mathcal{D}(G)$ of a graph $G$ is the matrix containing the pairwise distances between vertices, and the distance Laplacian matrix is $\mathcal{D}^L(G)=T(G)-\mathcal{D}(G)$, where $T(G)$ is the diagonal matrix of row sums of $\mathcal{D}(G)$. We establish several general methods for producing $\mathcal{D}^L$-cospectral graphs that can be used to construct infinite families. We provide examples showing that various properties are not preserved by $\mathcal{D}^L$-cospectrality, including examples of $\mathcal{D}^L$-cospectral strongly regular and circulant graphs. We establish that the absolute values of coefficients of the distance Laplacian characteristic polynomial are decreasing, i.e., $|\delta^L_{1}|\geq \dots \geq |\delta^L_{n}|$ where $\delta^L_{k}$ is the coefficient of $x^k$., Comment: 18 pages
- Published
- 2018
25. The Slater and sub-k-domination number of a graph with applications to domination and k-domination
- Author
-
John Asplund, Randy Davila, Boris Brimkov, and David Amos
- Subjects
Domination analysis ,domination number ,Applied Mathematics ,slater number ,degree sequence index strategy ,Combinatorics ,sub-k-domination number ,k-domination number ,05c69 ,QA1-939 ,Discrete Mathematics and Combinatorics ,Graph (abstract data type) ,Mathematics - Abstract
In this paper we introduce and study a new graph invariant derived from the degree sequence of a graph G, called the sub-k-domination number and denoted subk(G). This invariant serves as a generalization of the Slater number; in particular, we show that subk(G) is a computationally efficient sharp lower bound on the k-domination number of G, and improves on several known lower bounds. We also characterize the sub-k-domination numbers of several families of graphs, provide structural results on sub-k-domination, and explore properties of graphs which are subk(G)-critical with respect to addition and deletion of vertices and edges.
- Published
- 2020
26. The zero forcing polynomial of a graph
- Author
-
Boris Brimkov, Rachel Kirsch, Michael Phillips, Ariel Keller, Kirk Boyer, Carolyn Reinhart, Daniela Ferrero, and Sean English
- Subjects
Polynomial ,05C31, 05C15 ,Applied Mathematics ,0211 other engineering and technologies ,021107 urban & regional planning ,G.2.1 ,0102 computer and information sciences ,02 engineering and technology ,G.2.2 ,01 natural sciences ,Unimodality ,Vertex (geometry) ,Combinatorics ,Counting problem ,Colored ,010201 computation theory & mathematics ,FOS: Mathematics ,Zero Forcing Equalizer ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Combinatorics (math.CO) ,Uniqueness ,Graph coloring ,Mathematics - Abstract
Zero forcing is an iterative graph coloring process, where given a set of initially colored vertices, a colored vertex with a single uncolored neighbor causes that neighbor to become colored. A zero forcing set is a set of initially colored vertices which causes the entire graph to eventually become colored. In this paper, we study the counting problem associated with zero forcing. We introduce the zero forcing polynomial of a graph $G$ of order $n$ as the polynomial $\mathcal{Z}(G;x)=\sum_{i=1}^n z(G;i) x^i$, where $z(G;i)$ is the number of zero forcing sets of $G$ of size $i$. We characterize the extremal coefficients of $\mathcal{Z}(G;x)$, derive closed form expressions for the zero forcing polynomials of several families of graphs, and explore various structural properties of $\mathcal{Z}(G;x)$, including multiplicativity, unimodality, and uniqueness., 23 pages
- Published
- 2018
27. Computational Approaches for Zero Forcing and Related Problems
- Author
-
Caleb C. Fast, Illya V. Hicks, and Boris Brimkov
- Subjects
FOS: Computer and information sciences ,Information Systems and Management ,Discrete Mathematics (cs.DM) ,General Computer Science ,Computer science ,Computation ,G.1.6 ,0211 other engineering and technologies ,02 engineering and technology ,G.2.2 ,Management Science and Operations Research ,Industrial and Manufacturing Engineering ,0502 economics and business ,FOS: Mathematics ,Zero Forcing Equalizer ,Applied mathematics ,Mathematics - Combinatorics ,Integer programming ,050210 logistics & transportation ,021103 operations research ,Forcing (recursion theory) ,05 social sciences ,Process (computing) ,Graph ,05C85, 90C10 ,Modeling and Simulation ,Combinatorics (math.CO) ,Computer Science - Discrete Mathematics - Abstract
In this paper, we propose computational approaches for the zero forcing problem, the connected zero forcing problem, and the problem of forcing a graph within a specified number of timesteps. Our approaches are based on a combination of integer programming models and combinatorial algorithms, and include formulations for zero forcing as a dynamic process, and as a set-covering problem. We explore several solution strategies for these models, test them on various types of graphs, and show that they are competitive with the state-of-the-art algorithm for zero forcing. Our proposed algorithms for connected zero forcing and for controlling the number of zero forcing timesteps are the first general-purpose computational methods for these problems, and are superior to brute force computation., 37 pages, 4 tables; computer code available in GitHub
- Published
- 2017
28. Connected power domination in graphs
- Author
-
Logan A. Smith, Derek Mikesell, and Boris Brimkov
- Subjects
Control and Optimization ,Domination analysis ,Computer science ,0211 other engineering and technologies ,0102 computer and information sciences ,02 engineering and technology ,G.2.2 ,05C69, 05C50, 05C57, 94C15 ,01 natural sciences ,Electric power system ,Dominating set ,FOS: Mathematics ,Mathematics - Combinatorics ,Discrete Mathematics and Combinatorics ,Integer programming ,Time complexity ,Discrete mathematics ,021103 operations research ,Applied Mathematics ,Cactus graph ,16. Peace & justice ,Computer Science Applications ,Vertex (geometry) ,Computational Theory and Mathematics ,010201 computation theory & mathematics ,Theory of computation ,Combinatorics (math.CO) ,MathematicsofComputing_DISCRETEMATHEMATICS - Abstract
The study of power domination in graphs arises from the problem of placing a minimum number of measurement devices in an electrical network while monitoring the entire network. A power dominating set of a graph is a set of vertices from which every vertex in the graph can be observed, following a set of rules for power system monitoring. In this paper, we study the problem of finding a minimum power dominating set which is connected; the cardinality of such a set is called the connected power domination number of the graph. We show that the connected power domination number of a graph is NP-hard to compute in general, but can be computed in linear time in cactus graphs and block graphs. We also give various structural results about connected power domination, including a cut vertex decomposition and a characterization of the effects of various vertex and edge operations on the connected power domination number. Finally, we present novel integer programming formulations for power domination, connected power domination, and power propagation time, and give computational results., Comment: 21 pages
- Published
- 2017
- Full Text
- View/download PDF
29. Connected distance-based rasterization of objects in arbitrary dimension
- Author
-
Valentin E. Brimkov, Reneta P. Barneva, and Boris Brimkov
- Subjects
Spanning tree ,Offset (computer science) ,Modeling and Simulation ,Digital geometry ,Geometry and Topology ,Topology ,Digital surface ,Computer Graphics and Computer-Aided Design ,Software ,Digitization ,Mathematics ,Distance based - Abstract
In this paper we investigate an approach for constructing a connected digitization of an object [email protected]?R^n by taking the integer points within an offset of S of a certain radius. We consider the cases when S is a curve, surface, and an arbitrary path-connected object. We determine the minimal value of the offset radius which guarantees connectivity of the digitization. We also derive conditions under which the offset digitization of a disconnected object is always connected.
- Published
- 2011
30. Chromatic and flow polynomials of generalized vertex join graphs and outerplanar graphs
- Author
-
Illya V. Hicks and Boris Brimkov
- Subjects
FOS: Computer and information sciences ,Discrete Mathematics (cs.DM) ,Joins ,0102 computer and information sciences ,G.2.2 ,Chromatic polynomial ,01 natural sciences ,Combinatorics ,Computer Science::Discrete Mathematics ,Outerplanar graph ,TheoryofComputation_ANALYSISOFALGORITHMSANDPROBLEMCOMPLEXITY ,FOS: Mathematics ,Wheel graph ,Discrete Mathematics and Combinatorics ,Mathematics - Combinatorics ,Chromatic scale ,0101 mathematics ,Time complexity ,Computer Science::Databases ,Mathematics ,Multiset ,Mathematics::Combinatorics ,Applied Mathematics ,010102 general mathematics ,Vertex (geometry) ,05C15 ,010201 computation theory & mathematics ,Combinatorics (math.CO) ,MathematicsofComputing_DISCRETEMATHEMATICS ,Computer Science - Discrete Mathematics - Abstract
A generalized vertex join of a graph is obtained by joining an arbitrary multiset of its vertices to a new vertex. We present a low-order polynomial time algorithm for finding the chromatic polynomials of generalized vertex joins of trees, and by duality we find the flow polynomials of arbitrary outerplanar graphs. We also present closed formulas for the chromatic and flow polynomials of vertex joins of cliques and cycles, otherwise known as "generalized wheel" graphs., 14 pages
- Published
- 2015
31. Geometric Approach to Biosequence Analysis
- Author
-
Valentin E. Brimkov and Boris Brimkov
- Subjects
Simple (abstract algebra) ,Significant difference ,String (computer science) ,Biosequence ,Linearity ,Algorithm ,Mathematics - Abstract
Tools that effectively analyze and compare sequences are of great importance in various areas of applied computational research, especially in the framework of molecular biology. In the present paper, we introduce simple geometric criteria based on the notion of string linearity and use them to compare DNA sequences of various organisms, as well as to distinguish them from random sequences. Our experiments reveal a significant difference between biosequences and random sequences the former having much higher deviation from linearity than the latter as well as a general trend of increasing deviation from linearity between primitive and biologically complex organisms. The proposed approach is potentially applicable to the construction of dendograms representing the evolutionary relationships among species.
- Published
- 2014
32. Offset Approach to Defining 3D Digital Lines
- Author
-
François de Vieilleville, Reneta P. Barneva, Boris Brimkov, and Valentin E. Brimkov
- Subjects
Combinatorics ,Parallelepiped ,Offset (computer science) ,Digital line ,Digital geometry ,Geometry ,Mathematics - Abstract
In this paper we investigate an approach of constructing a 3D digital line by taking the integer points within an offset of a certain radius of the line. Alternatively, we also investigate digital lines obtained through a "pseudo-offset" defined by a parallelepiped enclosing the integer points around the line. We show that if the offset radius (resp. side of the parallelepiped section) is greater than $\sqrt{3}$ (resp. 2$\sqrt{3}$), then the digital line is at least 1-connected. Extensive experiments show that the lines obtained feature satisfactory appearance.
- Published
- 2008
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.