Search

The problem of deriving lower and upper bounds for the edit distance between undirected, labeled graphs has recently received increasing attention. However, only one algorithm has been proposed that allegedly computes not only an upper but also a lower bound for non-uniform edit costs and incorporates information about both node and edge labels. In this paper, we demonstrate that this algorithm is incorrect. We present a corrected version $\mathsf {B\scriptstyle{RANCH}}$ that runs in $\mathcal{O}(n^2\Delta ^3+n^3)$ time, where $\Delta$ is the maximum of the maximum degrees of input graphs $G$ and $H$ . We also develop a speed-up $\mathsf {B\scriptstyle{RANCH}}\mathsf{F\scriptstyle{AST}}$ that runs in $\mathcal{O}(n^2\Delta ^2+n^3)$ time and computes an only slightly less accurate lower bound. The lower bounds produced by $\mathsf {B\scriptstyle{RANCH}}$ and $\mathsf {B\scriptstyle{RANCH}}\mathsf{F\scriptstyle{AST}}$ are shown to be pseudo-metrics on a collection of graphs. Finally, we suggest an anytime algorithm $\mathsf {B\scriptstyle{RANCH}}\mathsf{T\scriptstyle{IGHT}}$ that iteratively improves $\mathsf {B\scriptstyle{RANCH}}$ ’s lower bound. $\mathsf {B\scriptstyle{RANCH}}\mathsf{T\scriptstyle{IGHT}}$ runs in $\mathcal{O}(n^3\Delta ^2+I(n^2\Delta ^3+n^3))$ time, where the number of iterations $I$ is controlled by the user. A detailed experimental evaluation shows that all suggested algorithms are Pareto optimal, that they are very effective when used as filters for edit distance range queries, and that they perform excellently when used within classification frameworks.

The irregularity of a simple graph G = ( V , E ) is defined as irr ( G ) = ∑ u v ∈ E ( G ) | d G ( u ) − d G ( v ) | , where dG(u) denotes the degree of a vertex u ∈ V(G). This graph invariant, introduced by Albertson in 1997, is a measure of the defect of regularity of a graph. Recently, it also gains interest in Chemical Graph Theory, where it is named the third Zagreb index. In this paper, by means of the Laplacian eigenvalues and the normalized Laplacian eigenvalues of G, we establish some new spectral upper bounds for irr(G). We then compare these new bounds with a known bound by Goldberg, and it turns out that our bounds are better than the Goldberg bound in most cases. We also present two spectral lower bounds on irr(G).

Let G be a complex unit gain graph which is obtained from an undirected graph Γ by assigning a complex unit φ ( v i v j ) to each oriented edge v i v j such that φ ( v i v j ) φ ( v j v i ) = 1 for all edges. The Laplacian matrix of G is defined as L ( G ) = D ( G ) − A ( G ) , where D ( G ) is the degree diagonal matrix of Γ and A ( G ) = ( a i j ) has a i j = φ ( v i v j ) if v i is adjacent to v j and a i j = 0 otherwise. In this paper, we provide a combinatorial description of det ( L ( G ) ) that generalizes that for the determinant of the Laplacian matrix of a signed graph.

A Hamiltonian graph G is hyper-Hamiltonian if G − v is Hamiltonian for any v ∈ V ( G ) . In this paper, we give some sufficient conditions for a graph to be hyper-Hamiltonian. We provide both, spectral and non-spectral conditions for hyper-Hamiltonicity.

The aim of edge editing or modification problems is to change a given graph by adding and deleting of a small number of edges in order to satisfy a certain property. We consider the Edge Editing to a Connected Graph of Given Degrees problem that asks for a graph G, non-negative integers d,k and a function \delta:V(G)->{1,...,d}, whether it is possible to obtain a connected graph G' from G such that the degree of v is \delta(v) for any vertex v by at most k edge editing operations. As the problem is NP-complete even if \delta(v)=2, we are interested in the parameterized complexity and show that Edge Editing to a Connected Graph of Given Degrees admits a polynomial kernel when parameterized by d+k. For the special case \delta(v)=d, i.e., when the aim is to obtain a connected d-regular graph, the problem is shown to be fixed parameter tractable when parameterized by k only., Comment: Some proofs are simplified and typos are corrected in this version

The concept of k-connectivity κk(G), introduced by Chartrand in 1984, is a generalization of the cut-version of the classical connectivity. For an integer k ≥ 2, the k-connectivity of a connected graph G with order n ≥ k is the smallest number of vertices whose removal from G produces a graph with at least k components or a graph with fewer than k vertices. In this paper, we get a sharp upper bound for the size of G with κk(G) = t, where 1 ≤ t ≤ n − k and k ≥ 3; moreover, the unique extremal graph is given. Based on this result, we get the exact values for the maximum size, denoted by g(n, k, t), of a connected graph G with order n and κk(G) = t. We also compute the exact values and bounds for another parameter f(n, k, t) which is defined as the minimum size of a connected graph G with order n and κk(G) = t, where 1 ≤ t ≤ n − k and k ≥ 3.

A graph G (V, E) is said to be a sum graph if there exists a bijective labeling from the vertex set V to a set S of positive integers such that (x y) ∈ E if and only if f(x) + f(y) ∈ S. In this paper, for a given graph G (V, E), the edge function, the edge product function and the edge product graph are introduced and studied. The edge product number of a graph is defined and the edge product numbers of paths is found.

The quadratic pencil of Sturm–Liouville operators on a star-shaped graph is investigated. We suppose that the coefficients of the pencil are known for all the edges of the graph except one, and study the partial inverse problem, which consists in recovering the remaining coefficients from the part of the spectrum. We prove the uniqueness theorem and provide a constructive algorithm for the solution of the partial inverse problem.

We propose a heuristic approximation algorithm for the 1-median problem. The 1-median problem is the problem of finding a vertex with the highest closeness centrality. Starting from a randomly selected vertex, our algorithm repeats to find a vertex with higher closeness centrality by approximately calculating closeness centrality of each vertex using simpler spanning subgraphs, which are called k-neighbor dense shortest path graphs with shortcuts. According to our experimental results using real networks with more than 10,000 vertices, our algorithm is more than 100 times faster than the exhaustive search and more than 20 times faster than the state-of-the-art approximation algorithm using annotated information to the vertices while the solutions output by our algorithm have higher approximation ratio.

We present an algorithm to support the dynamic embedding in the plane of a dynamic graph. An edge can be inserted across a face between two vertices on the face boundary (we call such a vertex pair linkable), and edges can be deleted. The planar embedding can also be changed locally by flipping components that are connected to the rest of the graph by at most two vertices. Given vertices $u,v$, linkable$(u,v)$ decides whether $u$ and $v$ are linkable in the current embedding, and if so, returns a list of suggestions for the placement of $(u,v)$ in the embedding. For non-linkable vertices $u,v$, we define a new query, one-flip-linkable$(u,v)$ providing a suggestion for a flip that will make them linkable if one exists. We support all updates and queries in O(log$^2 n$) time. Our time bounds match those of Italiano et al. for a static (flipless) embedding of a dynamic graph. Our new algorithm is simpler, exploiting that the complement of a spanning tree of a connected plane graph is a spanning tree of the dual graph. The primal and dual trees are interpreted as having the same Euler tour, and a main idea of the new algorithm is an elegant interaction between top trees over the two trees via their common Euler tour., Comment: Announced at STACS'15

Let G=(V,E), V={1,2,,n} be a simple graph without isolated vertices, with n(n3) vertices and m edges, whose vertex degrees are given in the following form d1d2dn>0. If A is the adjacency matrix, the Randi matrix R=Rij is defined in the following way Rij={1didjifviandvjareadjacent,0otherwise. The eigenvalues of matrix R, 12n, are called the Randi eigenvalues of graph G. The Randi energy of graph G, denoted by RE, is defined in the following way: RE=RE(G)=i=1n|i|. In this paper, upper bounds for graph invariant RE have been studied.

This paper investigates the problem of optimally determining source-destination connectivity in random networks. Viewing the network as a random graph, we start by investigating the Erdos–Renyi (ER) graph, as well as a structured graph where, interesting, the problem appears to be open. The problem examined is that of determining whether a given pair of nodes, a source $S$ , and a destination $D$ are connected by a path. Assuming that at each step one edge can be tested to see if it exists or not, we determine an optimal policy that minimizes the total expected number of steps. The optimal policy has several interesting features. In order to establish the connectivity of $S$ and $D$ , a policy needs to check all edges on some path to see if they all exist, but to establish the disconnectivity it has to check all edges on some cut to see if none of them exists. The optimal policy has the following form. At each step, it examines the condensation multigraph formed by contracting each known connected component to a single node, and then checks an edge that is simultaneously on a shortest $S$ – $D$ path as well as in a minimum $S$ – $D$ cut. Among such edges, it chooses that which lead to the most opportunities for connection. Interestingly, for an ER graph with $n$ nodes, where there is an edge between two nodes with probability $p$ , the optimal strategy does not depend on $p$ or $n$ , even though the entire graph itself undergoes a sharp transition from disconnectivity to connectivity around $p = \ln n/n$ . The policy is efficiently implementable, requiring no more than $30\log _{2} n$ operations to determine which edge to test next. The result also extends to some more general graphs and, meanwhile, provide useful insights into the connectivity determination in random networks.

Let G be a graph of order n. For i = 1 , 2 , ź , n , let di be the degree of the vertex vi of G. The extended adjacency matrix Aex of G is defined so that its (i, j)-entry is equal to 1 2 ( d i d j + d j d i ) if the vertices vi and vj are adjacent, and 0 otherwise,Yang etźal. (1994). The spectral radius ź1 and the energy E e x of the Aex-matrix are examined. Lower and upper bounds on ź1 and E e x are obtained, and the respective extremal graphs characterized.

We study the problem of structural graph clustering, a fundamental problem in managing and analyzing graph data. Given an undirected unweighted graph, structural graph clustering is to assign vertices to clusters, and to identify the sets of hub vertices and outlier vertices as well, such that vertices in the same cluster are densely connected to each other while vertices in different clusters are loosely connected. In this paper, we develop a new two-step paradigm for scalable structural graph clustering based on our three observations. Then, we present a $\mathsf {pSCAN}$ approach, within the paradigm, aiming to reduce the number of structural similarity computations, and propose optimization techniques to speed up checking whether two vertices are structure-similar. $\mathsf {pSCAN}$ outputs exactly the same clusters as the existing approaches $\mathsf {SCAN}$ and $\mathsf {SCAN\text{++}}$ , and we prove that $\mathsf {pSCAN}$ is worst-case optimal. Moreover, we propose efficient techniques for updating the clusters when the input graph dynamically changes, and we also extend our techniques to other similarity measures, e.g., Jaccard similarity. Performance studies on large real and synthetic graphs demonstrate the efficiency of our new approach and our dynamic cluster maintenance techniques. Noticeably, for the twitter graph with 1 billion edges, our approach takes 25 minutes while the state-of-the-art approach cannot finish even after 24 hours.

Within a study of scheduling problems with gaps, Chrobak et al. (CIAC 2015) have shown how to find γ points on the line that hit a maximum number of intervals, in a given family of n intervals, in O ( γ n 2 ) time. The problem is equivalent to finding γ cliques in an interval graph that cover a maximum number of distinct vertices. We give refined algorithms that run faster if the interval graph of the family is sparse.

We study the problem of discrepancy maximization on graphs: given a set of nodes $Q$ of an underlying graph $G$ , we aim to identify a connected subgraph of $G$ that contains many more nodes from $Q$ than other nodes. This variant of the discrepancy-maximization problem extends the well-known notion of “bump hunting” in the Euclidean space [1] . We consider the problem under two access models. In the unrestricted-access model, the whole graph $G$ is given as input, while in the local-access model we can only retrieve the neighbors of a given node in $G$ using a possibly slow and costly interface. We prove that the basic problem of discrepancy maximization on graphs is $\mathbf {NP}$ -hard, and empirically evaluate the performance of four heuristics for solving it. For the local-access model, we consider three different algorithms that aim to recover a part of $G$ large enough to contain an optimal solution, while using only a small number of calls to the neighbor-function interface. We perform a thorough experimental evaluation in order to understand the trade offs between the proposed methods and their dependencies on characteristics of the input graph.

Dictionary learning (DL) techniques aim to find sparse signal representations that capture prominent characteristics in a given data. Such methods operate on a data matrix $Y\in \mathbb {R}^{N\times M}$ , where each of its columns $y_i\in \mathbb {R}^N$ constitutes a training sample, and these columns together represent a sampling from the data manifold. For signals $y\in \mathbb {R}^N$ residing on weighted graphs, an additional challenge is incorporating the underlying geometric structure of the data domain into the learning process. In such cases, the topological graph structure may provide a crucial interpretation for the columns, while the data manifold itself may also possess a low-dimensional intrinsic structure that should be taken into account. In this work, we propose a novel dictionary learning algorithm for graph signals that simultaneously takes into account the underlying structure in both the signal and the manifold domains. Specifically, we require that the dictionary atoms are smooth with respect to the graph topology, as encapsulated by the graph Laplacian matrix. Furthermore, we propose to learn this graph Laplacian within the dictionary learning process, adapting it to promote the desired smoothness. Utilizing the manifold structure, we propose to encourage the smoothness of the sparse representations on the data manifold in a similar manner. Both these smoothness forces implicitly enhance the learned dictionary. The efficiency of the proposed approach is demonstrated on synthetic examples as well as on real data, showing that it outperforms other dictionary learning methods in typical problems such as resistance to noise and data completion.

Over years, virtual backbone has attracted lots of attention as a promising approach to deal with the broadcasting storm problem in wireless networks. Frequently, the problem of a quality virtual backbone is formulated as a variation of the minimum connected dominating set problem. However, a virtual backbone computed in this way is not resilient against topology change since the induced graph by the connected dominating set is one-vertex-connected. As a result, the minimum $k$ -connected $m$ -dominating set problem is introduced to construct a fault-tolerant virtual backbone. Currently, the best known approximation algorithm for the problem in unit disk graph by Wang assumes $k \leq 3$ and $m \geq 1$ , and its performance ratio is 280 when $k = m = 3$ . In this paper, we use a classical result from graph theory, Tutte decomposition, to design a new approximation algorithm for the problem in unit disk graph for $k \leq 3$ and $m \geq 1$ . In particular, the algorithm features with (a) a drastically simple structure and (b) a much smaller performance ratio, which is nearly 62 when $k = m = 3$ . We also conduct simulation to evaluate the performance of our algorithm.

In the classical Node-Disjoint Paths (NDP) problem, the input consists of an undirected $n$-vertex graph $G$, and a collection $\mathcal{M}=\{(s_1,t_1),\ldots,(s_k,t_k)\}$ of pairs of its vertices, called source-destination, or demand, pairs. The goal is to route the largest possible number of the demand pairs via node-disjoint paths. The best current approximation for the problem is achieved by a simple greedy algorithm, whose approximation factor is $O(\sqrt n)$, while the best current negative result is an $\Omega(\log^{1/2-\delta}n)$-hardness of approximation for any constant $\delta$, under standard complexity assumptions. Even seemingly simple special cases of the problem are still poorly understood: when the input graph is a grid, the best current algorithm achieves an $\tilde O(n^{1/4})$-approximation, and when it is a general planar graph, the best current approximation ratio of an efficient algorithm is $\tilde O(n^{9/19})$. The best currently known lower bound on the approximability of both these versions of the problem is APX-hardness. In this paper we prove that NDP is $2^{\Omega(\sqrt{\log n})}$-hard to approximate, unless all problems in NP have algorithms with running time $n^{O(\log n)}$. Our result holds even when the underlying graph is a planar graph with maximum vertex degree $3$, and all source vertices lie on the boundary of a single face (but the destination vertices may lie anywhere in the graph). We extend this result to the closely related Edge-Disjoint Paths problem, showing the same hardness of approximation ratio even for sub-cubic planar graphs with all sources lying on the boundary of a single face.

$$\mathcal {L}_1$$ graph is an effective way to represent data samples in many graph-oriented machine learning applications. Its original construction algorithm is nonparametric, and the graphs it generates may have high sparsity. Meanwhile, the construction algorithm also requires many iterative convex optimization calculations and is very time-consuming. Such characteristics would severely limit the application scope of $$\mathcal {L}_1$$ graph in many real-world tasks. In this paper, we design a greedy algorithm to speed up the construction of $$\mathcal {L}_1$$ graph. Moreover, we introduce the concept of “Ranked Dictionary” for $$\mathcal {L}_1$$ minimization. This ranked dictionary not only preserves the locality but also removes the randomness of neighborhood selection during the process of graph construction. To demonstrate the effectiveness of our proposed algorithm, we present our experimental results on several commonly used datasets using two different ranking strategies: One is based on Euclidean distance, and another is based on diffusion distance.

A graph clustering problem is under study (also known as the graph approximation problem) with a constraint on cluster sizes. Some new approximation algorithm is presented for this problem, and performance guarantee of the algorithm is obtained. It is shown that the problem belongs to the class APX for every fixed p, where p is the upper bound on the cluster sizes.

The M inimum L inear A rrangement (MLA) problem involves embedding a given graph on the integer line so that the sum of the edge lengths of the embedded graph is minimized. Most layout problems are either intractable or not known to be tractable, parameterized by the treewidth of the input graph. We investigate MLA with respect to three parameters that provide more structure than treewidth. In particular, we give a factor (1 + ε)-approximation algorithm for MLA parameterized by (ε, k ), where k is the vertex cover number of the input graph. By a similar approach, we obtain two FPT algorithms that exactly solve MLA parameterized by, respectively, the max leaf and edge clique cover numbers of the input graph.

In this paper we have computed minimum covering Seidel energies ofa star graph, complete graph, crown graph, complete bipartite graph and cocktailparty graphs. Upper and lower bounds for minimum covering Seidel energies of agraphs are also established.DOI : http://dx.doi.org/10.22342/jims.22.1.234.71-82

The paper considers the minimization of the sum of weights of edges forming a subset U? ? U of the set of disjoint simple cycles at vertices ? ∈ V in graph H = (V,U) and covering V. The problem under study (2-f problem) is polynomially solvable in algorithms that are characterized by technical difficulties that hinder the acceleration of computing. The 2-f problem is solved by reducing it to a simpler bipartite case. The result is represented by a perfect matching of bipartite graph corresponding to the solution of the assignment problem, where each circuit of cyclic expansion contains at least three arcs.

For every simple connected graph, we present a polynomial time algorithm for computing a numerical index, which is composed of primary and secondary parts. Given a graph $G=(V,E)$ where $V$ and $E$ are, respectively, vertex and edge sets, the primary part of the index is a set of $\vert V \vert $ fractions and the secondary part of the index is a set of $\vert B\vert \times \vert V\vert $ fractions, where $B$ is the partition of the vertex set $V$ . Basically, each fraction in the primary and secondary parts is the electrical resistance between two vertices when every edge in the graph is replaced with a unit resistor (1 $\Omega $ ). The experimental results show that our indexing algorithm produced a unique index for every simple connected graph with ≤10 vertices, including all graphs that are counterexamples for detecting graph isomorphism by resistance spectrum comparison. The strength of our indexing algorithm lies in its extreme simplicity. An index of a graph is solely derived from the determinants of reduced Laplacian matrices, which represent the graph. Therefore, the performance of our indexing algorithm only depends on how fast the matrix determinants can be computed.

In the paper we consider degree, spectral, and semidefinite bounds on the stability number of a graph. The bounds are obtained via reformulations and variants of the inverse theta function, a notion recently introduced by the author in a previous work.

Let G be a simple, undirected graph. Positive semidefinite (PSD) zero forcing on G is based on the following color-change rule: Let W 1 , W 2 , ? , W k be the sets of vertices of the k connected components in G - B (where B is a set of blue vertices). If w ? W i is the only white neighbor of some b ? B in the graph G B ? W i , then we change w to blue. A minimum positive semidefinite zero forcing set (PSDZFS) is a set of blue vertices that colors the entire graph blue and has minimum cardinality. The PSD propagation time of a PSDZFS B of graph G is the minimum number of iterations that it takes to color the entire graph blue, starting with B blue, such that at each iteration as many vertices are colored blue as allowed by the color-change rule. The minimum and maximum PSD propagation times are taken over all minimum PSD zero forcing sets of the graph. It is conjectured that every propagation time between the minimum and maximum propagation time is attainable by some minimum PSDZFS (this is not the case for the standard color-change rule). Tools are developed that aid in the computation of PSD propagation time. Several graph families and graphs with extreme PSD propagation times ( | G | - 2 , | G | - 1 , 1 , 0 ) are analyzed.

We develop a linear-space O(n+m) time algorithm to solve the cluster editing problem for proper interval models, where n and m are the number of vertices and edges of the represented graph. Fil: Lin, Min Chih. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales. Departamento de Computación; Argentina Fil: Soulignac, Francisco Juan. Universidad Nacional de Quilmes. Departamento de Ciencia y Tecnología; Argentina. Consejo Nacional de Investigaciones Científicas y Técnicas; Argentina Fil: Szwarcfiter, Jayme L.. Universidade Federal do Rio de Janeiro; Brasil

An embedding of a guest graph G over a host graph H is an injective map Φ from the vertices of G to the vertices of H and a routing map ρ, which associates every edge e = x y in G to a Φ ( x ) - Φ ( y ) path ρ ( e ) in H. Given an edge f in H the number of edges e in G such that f belongs to ρ ( e ) is the (edge) congestion cong(f) of f. The length of ρ ( e ) is called the dilatation dil(e) of e. The sum of all th dilatations is the cost of the embedding. The removal of an edge f of H gives rise to a surviving graph G f , consisting of the guest graph without those edges that cross f, i.e., G f = G − { e : f ∈ ρ ( e ) } . Given n and b, we are facing the problem of finding a minimum cost embedding Φ of a graph G with n vertices over the cycle C n , such that for any surviving graph G f , there is an embedding of the complete graph K n over G f whose congestions are not greater than b. This work presents a lower bound for the optimal cost of such problem and a family of embeddings that match this bound over a broad range of combinations of n and b.

For a graph $$G=(V,E)$$G=(V,E) the minimum line-distortion problem asks for the minimum k such that there is a mapping f of the vertices into points of the line such that for each pair of vertices x, y the distance on the line $$|f(x) - f(y)|$$|f(x)-f(y)| can be bounded by the term $$d_G(x, y)\le |f(x)-f(y)|\le k \, d_G(x, y)$$dG(x,y)≤|f(x)-f(y)|≤kdG(x,y), where $$d_G(x, y)$$dG(x,y) is the distance in the graph. The minimum bandwidth problem minimizes the term $$\max _{uv\in E}|f(u)-f(v)|$$maxuvźE|f(u)-f(v)|, where f is a mapping of the vertices of G into the integers $$\{1, \ldots , n\}$${1,ź,n}. We investigate the minimum line-distortion and the minimum bandwidth problems on unweighted graphs and their relations with the minimum length of a Robertson---Seymour's path-decomposition. The length of a path-decomposition of a graph is the largest diameter of a bag in the decomposition. The path-length of a graph is the minimum length over all its path-decompositions. In particular, we show:there is a simple polynomial time algorithm that embeds an arbitrary unweighted input graph G into the line with distortion $$\mathcal{O}(k^2)$$O(k2), where k is the minimum line-distortion of G;if a graph G can be embedded into the line with distortion k, then G admits a Robertson---Seymour's path-decomposition with bags of diameter at most k in G;for every class of graphs with path-length bounded by a constant, there exist an efficient constant-factor approximation algorithm for the minimum line-distortion problem and an efficient constant-factor approximation algorithm for the minimum bandwidth problem;there is an efficient 2-approximation algorithm for computing the path-length of an arbitrary graph;AT-free graphs and some intersection families of graphs have path-length at most 2;for AT-free graphs, there exist a linear time 8-approximation algorithm for the minimum line-distortion problem and a linear time 4-approximation algorithm for the minimum bandwidth problem.

Using graph products we present an O ( | V | 2 | E | + | V | 3 log | V | ) separation algorithm for the nonsimple 1 -wheel inequalities by Cheng and Cunningham (1997) of the stable set polytope, which is faster than their O ( | V | 4 ) algorithm.There are two ingredients for our algorithm. The main improvement stems from a reduction of the separation problem to multiple shortest path problems in an auxiliary graph having only 6 | V | vertices and 9 | E | arcs, thereby preserving low sparsity. Then Johnson's algorithm can be applied to the auxiliary graph of same sparsity as the original one.In contrast, Cheng and Cunningham's auxiliary graph is by construction dense, | E | = O ( | V | 2 ) , so application of Johnson's algorithm provides no large improvement.

In this paper, we study the parallel and the space complexity of the graph isomorphism problem (\(\mathsf {GI}\)) for several parameterizations.

A planar 3-connected graph $G$ is called \emph{essentially $4$-connected} if, for every 3-separator $S$, at least one of the two components of $G-S$ is an isolated vertex. Jackson and Wormald proved that the length $\mathop{\rm circ}\nolimits(G)$ of a longest cycle of any essentially 4-connected planar graph $G$ on $n$ vertices is at least $\frac{2n+4}{5}$ and Fabrici, Harant and Jendrol' improved this result to $\mathop{\rm circ}\nolimits(G)\geq \frac{1}{2}(n+4)$. In the present paper, we prove that an essentially 4-connected planar graph on $n$ vertices contains a cycle of length at least $\frac{3}{5}(n+2)$ and that such a cycle can be found in time $O(n^2)$.

The energy of a graph is the sum of the absolute values of its eigenvalues. We propose a new problem on graph energy change due to any single edge deletion. Then we survey the literature for existing partial solution of the problem, and mention a conjecture based on numerical evidence. Moreover, we prove in three different ways that the energy of a cycle graph decreases when an arbitrary edge is deleted except for the order of 4.

We consider the problem of finding interval graph representations that additionally respect given interval lengths and/or pairwise intersection lengths, which are represented as weight functions on the vertices and edges, respectively. Pe'er and Shamir (1997 [25] ) proved that the problem is NP -complete if only the former are given. For the case when both are given, Fulkerson and Gross (1965 [8] ) gave an O ( n 2 ) time algorithm; we improve this to O ( n + m ) time and supplement it with a logspace algorithm. For the case when only the latter are given, we give both an O ( n m ) time algorithm and a logspace algorithm. In all these bounds, n is the number of vertices and m is the number of edges in the input graph. Complementing their hardness result, Pe'er and Shamir give a polynomial-time algorithm for the case that the input graph has a unique interval ordering of its maximal cliques. For such graphs, their algorithm computes an interval representation (if it exists) that respects a given set of distance inequalities between the interval endpoints. We observe that deciding if such a representation exists is NL -complete.

The bandwidth minimization problem (BMP) has been classified as NP-complete because the polynomial time algorithm to find the optimal solution has been unknown yet. This paper suggests polynomial time heuristic algorithm is to find the solution of bandwidth minimization problem. To find the minimum bandwidth O * = min O(G), O(G) = max {│f(ν i )-f(ν i ) : ν i ,ν i ∈E} for given graph G=(V,E) m=│V│,n=│E│ the proposed algorithm sets the maximum degree vertex ν i in graph G into global central point (GCP), and labels the median value?m+1/2? between [1,m] range. The graph G is partitioned into subgroup, the maximum degree vertex in each subgroup is set to local central point(LCP), and we adjust the label of LCP per each subgroup as possible as minimum distance from GCP. The proposed algorithm requires O(mn) time complexity for label to all of vertices. For various twelve graph, the proposed algorithm can be obtains the same result as known optimal solution. For one graph, the proposed algorithm can be improve on known solution.

Since many graph data are often noisy and incomplete in real applications, it has become increasingly important to retrieve graphs $g$ in the graph database $D$ that approximately match the query graph $q$ , rather than exact graph matching. In this paper, we study the problem of graph similarity search, which retrieves graphs that are similar to a given query graph under the constraint of graph edit distance. We propose a systematic method for edit-distance based similarity search problem. Specifically, we derive two lower bounds, i.e., partition-based and branch-based bounds, from different perspectives. More importantly, a hybrid lower bound incorporating both ideas of the two lower bounds is proposed, which is theoretically proved to have higher (at least not lower) pruning power than using the two lower bounds together. We also present a uniform index structure, namely u-tree, to facilitate effective pruning and efficient query processing. Extensive experiments confirm that our proposed approach outperforms the existing approaches significantly, in terms of both the pruning power and query response time.

A zero-sum k-flow for a graph G is a vector in the null-space of the 0 , 1 -incidence matrix of G such that its entries belong to { ? 1 , ? , ? ( k - 1 ) } . Akbari et al. (2009) 5 conjectured that if G is a graph with a zero-sum flow, then G admits a zero-sum 6-flow. ( 2 , 3 ) -semiregular graphs are an important family in studying zero-sum flows. Akbari et al. (2009) 5 proved that if Zero-Sum Conjecture is true for any ( 2 , 3 ) -semiregular graph, then it is true for any graph. In this paper, we show that there is a polynomial time algorithm to determine whether a given ( 2 , 3 ) -graph G has a zero-sum 3-flow. In fact, we show that, there is a polynomial time algorithm to determine whether a given ( 2 , 4 ) -graph G with n vertices has a zero-sum 3-flow, where the number of vertices of degree four is O ( log ? n ) . Furthermore, we show that it is NP-complete to determine whether a given ( 3 , 4 ) -semiregular graph has a zero-sum 3-flow. A zero-sum k-flow for a graph G is a vector in the null-space of the 0 , 1 -incidence matrix of G such that its entries belong to { ? 1 , ? , ? ( k - 1 ) } .We show that it is NP-complete to determine whether a given ( 3 , 4 ) -semiregular graph has a zero-sum 3-flow.

In this paper we introduce the average reliability of a graph G , avgRel ( G ) , which is average value of the all terminal reliability of a graph G on [ 0 , 1 ] . We show that while the determination of the average reliability of a graph is apparently intractable, it can be efficiently bounded. We show that the closure of the average reliabilities is the interval [ 0 , 1 ] . Finally, while in general there do not exist uniformly optimal graphs with respect to reliability, we apply average reliability to propose “good” graphs for network reliability, and provide evidence that a specific family of cyclic graphs are indeed good.