1,720,974 research outputs found
The Inverse Eigenvalue Problem of a Graph
Full text linkHistorically, matrix theory and combinatorics have enjoyed a powerful, mutually beneficial relationship. Examples include: Perron-Frobenius theory describes the relationship between the combinatorial arrangement of the entries of a nonnegative matrix and the properties of its eigenvalues and eigenvectors (see [53, Chapter 8]). The theory of vibrations (e.g., of a system of masses connected by strings) provides many inverse problems (e.g., can the stiffness of the springs be prescribed to achieve a system with a given set of fundamental vibrations?) whose resolution intimately depends upon the families of matrices with a common graph (see [46, Chapter 7]).
The Inverse Eigenvalue Problem of a graph (IEP-G), which is the focus of this chapter, is another such example of this relationship. The IEP-G is rooted in the 1960s work of Gantmacher, Krein, Parter and Fielder, but new concepts and techniques introduced in the last decade have advanced the subject significantly and catalyzed several mathematically rich lines of inquiry and application. We hope that this chapter will highlight these new ideas, while serving as a tutorial for those desiring to contribute to this expanding area.This is a manuscript of a chapter published as Hogben, Leslie, Jephian C.-H. Lin, and Bryan L. Shader. “The Inverse Eigenvalue Problem of a Graph.” In 50 years of Combinatorics, Graph Theory, and Computing (Fan Chung, Ron Graham, Frederick Hoffman, Leslie Hogben, Ronald C. Mullin, and Douglas B. West, eds.). Boca Raton, FL: CRC Press, Taylor & Francis Group (2019): 239-262. Posted with permission.</p
A brief study of bi-R-diagonal pairs
No full textA. Nica and R. Speicher defined the R-diagonal element and found that the R-diagonal elements satisfy a \ue2free absorption\ue2 property, that is, if a is an R-diagonal element and is \ue2-free from b, then ab is also an R-diagonal element. Later, B. Krawczyk and R. Speicher studied the R-diagonal elements from a combinatorial perspective using free cumulants.
Since D. Voiculescu proposed the notion of bi-free independent, many concepts of free probability have been generalized into a bi-free probability version. For example, the bi-R-diagonal pair is the bi-free probability version of the R-diagonal element, which was first proposed by P. Skoufranis using bi-free cumulants.
We will survey these concepts
Eigenvalue multiplicities of Laplacian matrices
No full textFor a labeled graph, we may transform it into a matrix called the Laplacian matrix and study the relations between graphs and their Laplacian eigenvalues.
We focus on the second smallest Laplacian eigenvalue \uce\ubb2, which is also known as the algebraic connectivity. The eigenvector of \uce\ubb2 can be used for graph drawing, graph partitioning, and spectral clustering. Since the choices of the eigenvector can vary when the eigenvalue has a high multiplicity, this thesis studies the multiplicity of \uce\ubb2, aiming to understand the robustness of these applications.
We notice that the multiplicity of \uce\ubb2 is more than one for many graphs. We also study how to use the eigenvalue multiplicities of small graphs to obtain the eigenvalue multiplicities of their graph products. The graph operations we have considered include the disjoint union, the cartesian product, the corona product, and uni-join
Combinatorial approaches to compare Perron values.
No full textOur goal is to find the characteristic set of an unweighted tree, in a combinatorial way to avoid more tedious matrix calculations. One may determine the possible location of the characteristic set by looking at the graph and comparing the Perron values of each branch.
The original method of finding the characteristic set of the tree is based on the eigenvector corresponding to the second smallest eigenvalue of the Laplacian matrix. By viewing the vector as a function on the vertices, one may determine the position of characteristic set. Although this method is very intuitive, it requires solving the eigenvector with respect to the second smallest eigenvalue. If the number of the vertices of the tree is n, one has to diagonalize an n \uc3 n matrix to find the characteristic set. When n is large, it will be difficult to solve the eigenproblem. Therefore, there is another method that uses the bottleneck matrix of each branch and its Perron value to find the characteristic set. Both methods reach the characteristic set accurately. Through this method, the matrix to be calculated is of size at most n/2 \uc3 n/2, which is relatively small comparing to the first method.
The thesis is organized as follows. We will first review the basic properties of graph theory and some basic definitions of matrices. Next, we introduce the preliminaries of the Laplacian matrix, the bottleneck matrix, the characteristic set, and their properties. We revisit two known methods of finding the characteristic set, using the eigenvector and using the Perron value. Finally, our main result is to introduce a new way to compare the Perron values of two rooted trees. Through this technique, we may find the characteristics of small trees without solving the eigenproblem
A Vectorized Implementation for Zero Forcing Algorithms
No full textFor the simple graph whose vertices are either filled or unfilled, the color-change rule is that if a filled vertex has all of its neighbors filled except for one unfilled neighbor, then this unique unfilled neighbor will be filled at the next step. The zero forcing is an iterative process that propagates more filled vertices through the color-change rule. The zero forcing problem is how to forcing the all vertices in graph to be filled with the least initial filled vertices according to the color-change rule.
The Wavefront is an algorithmic approach to solve zero forcing problem. In this paper, we will introduce the Wavefront algorithm, expand the results to loop graphs, and implement them with NumPy
The study of fractional 1-eternal domination in graphs
No full textFractional domination and packing was first studied by S.M. Hedetniemi et al. and 1-eternal domination problem was first studied by A.P. Bruger et al. . In 1-eternal domination problem, we consider a graph G, each vertex of G can be stationed by an army. When a non-stationed vertex is attacked, it can be defensed by moving an army from a stationed adjacent vertex. If for any infinite sequence of attack can be defensed, we say that graph G can be eternally defensed by the army we have stationed on. In this thesis, we focus on 1-eternal domination problem with the guards on each vertex are allowed to be non-integer, and call it fractional 1-eternal domination problem. The fractional 1-eternal domination number of graph G is the minimum guards for defensing G by fractional 1-eternal domination. We find fractional 1-eternal domination number on several common graphs, such as paths, cycles, bipartite graphs, and also on two-cycle graphs
The study of eternal dominating set in graphs
No full textThe eternal domination problem was \uef\uacrst studied by A.P. Burger et al.
in [1]. Then W.Goddard, S.M.Hedetniemi, S.T.Hedetniemi in [2] introduced
the eternal domination problem with multiple guards moving. In this thesis,
we discuss the 1-eternal domination number, m-eternal domination number
in some graphs, and we give some Algorithms to \uef\uacnd a minimum 1-eternal
dominating set and a minimum m-eternal dominating set in a graph
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Spatially constrained clustering
No full textAt present, there is still lack of appropriate methods of clustering to apply on geographical
data, which not only effectively distinguish groups with significant difference
in the data, but take into account that the grouping blocks are geographically connected.
Existing methods nowadays cannot effectively distinguish those nongeographically
similar
data whose geographical locations are not close. This study provides two methods
to solve the above issue. The first method is hierarchical clustering with the connected
conditions and the second one creates a coordinate axis reflecting the path distance on the
undirected graph. According to the experimental results, these two methods both have
connectivity properties
- …
