For a connected
k
-uniform hypergraph
H
, let
A
α
(
H
)
=
α
D
(
H
)
+
(
1
-
α
)
A
(
H
)
, where
A
(
H
)
(resp.
D
(
H
)
) is its adjacency (resp. degree) tensor and
0
≤
α
<
1
. We call the least real ...eigenvalue of
A
α
(
H
)
having a real eigenvector as
α
-least eigenvalue of
H
. In this paper, we obtain some properties on
α
-least eigenvalue of
H
. As their applications, the extremal hypergraphs whose
α
-least eigenvalue attaining minimum are characterized among some classes of hypergraphs.
Given a simple graph G, let A(G) be its adjacency matrix. A principal submatrix of A(G) of order one less than the order of G is the adjacency matrix of its vertex deleted subgraph. It is well-known ...that the multiplicity of any eigenvalue of A(G) and such a principal submatrix can differ by at most one. Therefore, a vertex v of G is a downer vertex (neutral vertex, or Parter vertex) with respect to a fixed eigenvalue ? if the multiplicity of ? in A(G)?v goes down by one (resp., remains the same, or goes up by one). In this paper, we consider the problems of characterizing these three types of vertices under various constraints imposed on graphs being considered, on vertices being chosen and on eigenvalues being observed. By assigning weights to edges of graphs, we generalizeour results to weighted graphs, or equivalently to symmetric matrices.
The resistance distance was introduced by Klein and Randić as a generalization of the classical distance. The Kirchho index 𝐾𝑓(𝐺) of a graph 𝐺 is the sum of resistance distances between all ...unordered pairs of vertices. In this paper we determine the extremal graphs with minimal Kirchho index among all 𝑛-vertex graphs with 𝑘 cut vertices where
1
≤
k
<
n
2
.
The rapid development of data publishing and information access technology bring a growing number of problems in privacy leakage. In order to avoid linking attackshappened between attributes, ...K-anonymity model was proposed and become the most widely used in privacy preserving data publishing. Identification of quasi-identifiers (QIs) is one of the primary problems which will directly affect the effectiveness of K-anonymity method. However, most of the existing methods ignored this problem or just choose QIs empirically. These will greatly reduce the validity of K-anonymity method as well as the utility of anonymous data. In this paper, we study the problem of finding QIs for privacy preserving data publishing method based on K-anonymity model. Firstly, we analyze the roles of QIs from the view of independence of sets, and define it as a collection of attributes that can separate sensitive attributes from the other non-sensitive attributes. Then, we propose a construction method for attribute graph based on relationship matrix, which can represent potential connectivity of publishing data, published data and external knowledge. Finally, we put forward an identification algorithm for QIs based on the concept of cut-vertex, which is aiming to find the necessary and minimum QIs. The proposed algorithm is useful to avoid inconvenience and inaccuracy caused by artificial partition of QIs, and can be applied in data publishing situations with multiple sensitive attributes after some extension. Experiments and analysis show that the proposed identification algorithm has better partition ability and lower computational complexity. Therefore, it has good practical value in the application environment of publishing of big data.
The Wiener index is the sum of distances between all pairs of distinct vertices in a connected graph, which is the oldest topological index related to molecular branching. In this article, we give a ...condition to determine the graphs having the smallest Wiener index among all unicyclic graphs given number of pendant vertices, and we also determine the graphs having the smallest Wiener index among all unicyclic graphs given number of cut vertices.
A cut vertex is defined as a network node whose removal increases the number of network components. Failure of a cut vertex disconnects a network component and downgrades the network performance. ...Overlay networks are resilient to the failure of random nodes, but cut vertices that have been observed in real-world overlay traces make the network very vulnerable to well-constructed and targeted attacks. Traditional methods of detecting cut vertices are centralized and are very difficult, if not impossible, to be applied to large-scale and highly dynamic overlay networks. We aim to provide a practical solution by proposing a distributed mechanism that detects the cut vertices and neutralizes them to noncut vertices before they fail. The proposed mechanism not only minimizes the possibility of network decomposition on the cut vertex failure but also offloads the traffic that is handled by the cut vertices. We prove that our proposed method can correctly identify the cut vertices. We evaluate the performance of our design through trace-driven simulations. The results show that our method can successfully locate all cut vertices in the network and greatly offload the traffic processed by cut vertices.
Let
R
be a commutative ring. The annihilator graph of
R
, denoted by AG(
R
), is the undirected graph with all nonzero zero-divisors of
R
as vertex set, and two distinct vertices
x
and
y
are adjacent ...if and only if ann
R
(
xy
) ≠ ann
R
(
x
) ∪ ann
R
(
y
), where for
z
∈
R
, ann
R
(
z
) = {
r
∈
R
:
rz
= 0}. In this paper, we characterize all finite commutative rings
R
with planar or outerplanar or ring-graph annihilator graphs. We characterize all finite commutative rings
R
whose annihilator graphs have clique number 1, 2 or 3. Also, we investigate some properties of the annihilator graph under the extension of
R
to polynomial rings and rings of fractions. For instance, we show that the graphs AG(
R
) and AG(
T
(
R
)) are isomorphic, where
T
(
R
) is the total quotient ring of
R
. Moreover, we investigate some properties of the annihilator graph of the ring of integers modulo
n
, where
n
⩾ 1.
Connection and separation in hypergraphs Bahmanian, Mohammad A.; Sajna, Mateja
Theory and applications of graphs (Statesboro, Ga.),
12/2015, Letnik:
2, Številka:
2
Journal Article
Recenzirano
Odprti dostop
In this paper we study various fundamental connectivity properties of hypergraphs from a graph-theoretic perspective, with the emphasis on cut edges, cut vertices, and blocks. We prove a number of ...new results involving these concepts. In particular, we describe the exact relationship between the block decomposition of a hypergraph and the block decomposition of its incidence graph.
The geometric bottleneck Steiner network problem on a set of vertices X embedded in a normed plane requires one to construct a graph G spanning X and a variable set of k≥0 additional points, such ...that the length of the longest edge is minimised. If no other constraints are placed on G, then a solution always exists which is a tree. In this paper, we consider the Euclidean bottleneck Steiner network problem for k≤2, where G is constrained to be 2-connected. By taking advantage of relative neighbourhood graphs, Voronoi diagrams, and the tree structure of block cut-vertex decompositions of graphs, we produce exact algorithms of complexity O(n2) and O(n2logn) for the cases k=1 and k=2 respectively. Our algorithms can also be extended to other norms such as the Lp planes.
The Merrifield–Simmons index of a graph is defined as the total number of its independent sets, including the empty set. Denote by
G
(
n
,
k
)
the set of connected graphs with
n
vertices and
k
cut ...vertices. In this paper, we characterize the graphs with the maximum and minimum Merrifield–Simmons index, respectively, among all graphs in
G
(
n
,
k
)
for all possible
k
values.
PDF
