In a rooted graph, a vertex is designated as its root. An outerplanar graph is represented by a plane embedding such that all vertices appear along its outer boundary. Two different plane embeddings of a rooted outerp...
详细信息
In a rooted graph, a vertex is designated as its root. An outerplanar graph is represented by a plane embedding such that all vertices appear along its outer boundary. Two different plane embeddings of a rooted outerplanar graphs are called symmetric copies. Given integers n >= 3 and g >= 3, we give an O(n)-space and O(1)-time delay algorithm that generates all biconnected rooted outerplanar graphs with exactly n vertices such that the size of each inner face is at most g without delivering two symmetric copies of the same graph.
We consider an edge-weighted graph G with a designated vertex v(0) such that weights of edges incident to v(0) may increase or decrease. We show that, with an O(mn + n(2) log n) time preprocessing, a minimum cut of th...
详细信息
We consider an edge-weighted graph G with a designated vertex v(0) such that weights of edges incident to v(0) may increase or decrease. We show that, with an O(mn + n(2) log n) time preprocessing, a minimum cut of the current G can be computed in O(log n) time per update of weight of any edge (v(0), u).
Let c be a proper edge coloring of a graph G. If there exists no bicolored cycle in G with respect to c, then c is called an acyclic edge coloring of G. Let G be a planar graph with maximum degree Delta and girth g. I...
详细信息
Let c be a proper edge coloring of a graph G. If there exists no bicolored cycle in G with respect to c, then c is called an acyclic edge coloring of G. Let G be a planar graph with maximum degree Delta and girth g. In Dong and Xu (2010) [8], Dong and Xu proved that G admits an acyclic edge coloring with Delta(G) colors if Delta >= 8 and g >= 7, or Delta >= 6 and g >= 8, or Delta >= 5 and g >= 9, or Delta >= 4 and g >= 10, or Delta >= 3 and g >= 14. In this note, we fix a small gap in the proof of Dong and Xu (2010) [8], and generalize the above results to toroidal graphs. (C) 2011 Elsevier B.V. All rights reserved.
Polynomial algorithms are given for the following two problems: given a graph with n vertices and m edges, find a complete balanced bipartite subgraph K(q,q) with q = right perpendicularln n/ln(2en(2)/m)left perpendic...
详细信息
Polynomial algorithms are given for the following two problems: given a graph with n vertices and m edges, find a complete balanced bipartite subgraph K(q,q) with q = right perpendicularln n/ln(2en(2)/m)left perpendicular. given a graph with n vertices, find a decomposition of its edges into complete balanced bipartite graphs having altogether O(n(2)/ln n) vertices. The first algorithm can be modified to have running time linear in m and find a K(q',q') with q' = right perpendicularq/5left perpendicular. Previous proofs of the existence of such objects, due to Kovari, Sos and Turin (1954) [10], Chung, Erdos and Spencer (1983) [5], Bublitz (1986) [4] and Tuza (1984) [13] were non-constructive. (C) 2009 Elsevier B.V. All rights reserved.
The Wiener index is the most popular topological index used as an invariant molecular descriptor in the study of structures and physiochemical properties of molecules. Here, Wiener index and its modifications, hyper-W...
详细信息
The Wiener index is the most popular topological index used as an invariant molecular descriptor in the study of structures and physiochemical properties of molecules. Here, Wiener index and its modifications, hyper-Wiener and Harary indices, as well as Hosoya and hyper-Hosoya polynomials are studied over C-84 fullerene nanocage which is the third most abundant member of the higher fullerene series with two major structures known as stable C-84, D-2 (22) and D-2d (23). The computation of Wiener indices and polynomials of isomers C-84-D-2 (22) and C-84-D-2d (23) is implemented using graph algorithms which employ the isomer's molecular graphs. Our results show that the isomer C-84-D-2 (22) has greater Wiener and topological efficiency indices than isomer C-84-D-2d (23), which indicates that the isomer C-84-D-2d (23) has greater compactness and stability than isomer C-84-D-2 (22). These results are consistent with the experimental observations and further confirmed by the lower Harary index of isomer C-84-D-2 (22). The greater Wiener index of isomer C-84-D-2 (22) also suggests that its boiling point would be higher than that of isomer C-84-D-2d (23).
A determinant property of the structure of a biological network is the distribution of local connectivity patterns, i.e., network motifs. In this work, a method for creating directed, unweighted networks while promoti...
详细信息
A determinant property of the structure of a biological network is the distribution of local connectivity patterns, i.e., network motifs. In this work, a method for creating directed, unweighted networks while promoting a certain combination of motifs is presented. This motif-based network algorithm starts with an empty graph and randomly connects the nodes by advancing or discouraging the formation of chosen motifs. The in-or out-degree distribution of the generated networks can be explicitly chosen. The algorithm is shown to perform well in producing networks with high occurrences of the targeted motifs, both ones consisting of three nodes as well as ones consisting of four nodes. Moreover, the algorithm can also be tuned to bring about global network characteristics found in many natural networks, such as small-worldness and modularity.
We study exak(n, F), the largest number of edges in an n-vertex graph that contains exactly k copies of a given subgraph F. The case k = 0 is the Turan number ex(n, F) that is among the most studied parameters in extr...
详细信息
We study exak(n, F), the largest number of edges in an n-vertex graph that contains exactly k copies of a given subgraph F. The case k = 0 is the Turan number ex(n, F) that is among the most studied parameters in extremal graph theory. We show that for any F and k, exak(n, F) = (1+o(1))ex(n, F) and determine the exact values of exak(n, K3) and exa1(n, Kr) for n large enough. We also explore a connection to the following well-known problem in search theory. We are given a graph of order n that consists of an unknown copy of F and some isolated vertices. We can ask pairs of vertices as queries, and the answer tells us whether there is an edge between those vertices. Our goal is to describe the graph using as few queries as possible. Aigner and Triesch in 1990 showed that the number of queries needed is at least (n ) - exa1(n, F). Among other results we show that the number of queries that were answered NO is at least (n 2 ) - exa1(n, F). 2 (c) 2023 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).
We study the problem of deciding reconfigurability of target sets of a graph. Given a graph G with vertex thresholds tau, consider a dynamic process in which vertex v becomes activated once at least tau(v) of its neig...
详细信息
We study the problem of deciding reconfigurability of target sets of a graph. Given a graph G with vertex thresholds tau, consider a dynamic process in which vertex v becomes activated once at least tau(v) of its neighbors are activated. A vertex set S is called a target set if all vertices of G would be activated when initially activating vertices of S. In the TARGET SET RECONFIGURATION problem, given two target sets X and Y of the same size, we are required to determine whether X can be transformed into Y by repeatedly swapping one vertex in the current set with another vertex not in the current set preserving every intermediate set as a target set. In this paper, we investigate the complexity of TARGET SET RECONFIGURATION in restricted cases. On the hardness side, we prove that TARGET SET RECONFIGURATION is PSPACE-complete on bipartite planar graphs of degree 3 and 4 and of threshold 2, bipartite 3-regular graphs and planar 3-regular graphs of threshold 1 and 2, and split graphs, which is in contrast to the fact that a special case called VERTEX COVER RECONFIGURATION is in P for the last graph class. On the positive side, we present a polynomial-time algorithm for TARGET SET RECONFIGURATION on graphs of maximum degree 2 and trees. The latter result can be thought of as a generalization of that for VERTEX COVER RECONFIGURATION.
In a graph, a matching cut is an edge cut that is a matching. MATCHING CUT is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP-complete. While Matching Cut is trivial fo...
详细信息
In a graph, a matching cut is an edge cut that is a matching. MATCHING CUT is the problem of deciding whether or not a given graph has a matching cut, which is known to be NP-complete. While Matching Cut is trivial for graphs with minimum degree at most one, it is NP-complete on graphs with minimum degree two. In this paper, we show that, for any given constant c > 1, Matching Cut is NP-complete in the class of graphs with minimum degree c and this restriction of Matching Cut has no subexponential-time algorithm in the number of vertices unless the Exponential-Time Hypothesis fails. We also show that, for any given constant. epsilon > 0, Matching Cut remains NP-complete in the class of n-vertex (bipartite) graphs with unbounded minimum degree delta > n(1-epsilon). We give an exact branching algorithm to solve Matching Cut for graphs with minimum degree delta >= 3 in O*(lambda(n)) time, where lambda is the positive root of the polynomial x(delta+1) - x(delta) - 1. Despite the hardness results, this is a very fast exact exponential-time algorithm for Matching Cut on graphs with large minimum degree;for instance, the running time is O*(1.0099(n)) on graphs with minimum degree delta >= 469. Complementing our hardness results, we show that, for any two fixed constants 1 < c < 4 and c' >= 0, Matching Cut is solvable in polynomial time for graphs with large minimum degree delta >= 1/c n - c'.
Advances in sequencing technologies are allowing genome-wide association studies at an ever-growing scale. The interpretation of these studies requires dealing with statistical and combinatorial challenges, owing to t...
详细信息
Advances in sequencing technologies are allowing genome-wide association studies at an ever-growing scale. The interpretation of these studies requires dealing with statistical and combinatorial challenges, owing to the multi-factorial nature of human diseases and the huge space of genomic markers that are being monitored. Recently, it was proposed that using protein protein interaction network information could help in tackling these challenges by restricting attention to markers or combinations of markers that map to close proteins in the network. In this review, we survey techniques for integrating genomic variation data with network information to improve our understanding of complex diseases and reveal meaningful associations. (C) 2013 Elsevier Ltd. All rights reserved.
暂无评论