Search

Björner, Lovász and Shor introduced a chip-firing game on a finite graph $$G$$ as follows. We put some chips on each vertex of $$G$$ , we say that a vertex is ready if it has at least as many chips as its degree, in which case we can fire it and the result is that it distributes one chip to each of its neighbors, this may cause other vertices to be ready, and so on. This game continues until no vertex can be fired. In this paper, we study chip-firing games on complete graphs. We obtain a sufficient and necessary condition for chip-firing games on complete graphs to be finite. [ABSTRACT FROM AUTHOR]

Let $$G$$ be a graph with degree sequence $$d_1,d_2,\ldots ,d_n$$ . Given a positive integer $$p$$ , denote by $$e_p(G)=\sum _{i=1}^n d_i^p$$ . Caro and Yuster introduced a Turán-type problem for $$e_p(G)$$ : given an integer $$p$$ , how large can $$e_p(G)$$ be if $$G$$ has no subgraph of a particular type. They got some results for the subgraph of particular type to be a clique of order $$r+1$$ and a cycle of even length, respectively. Denote by $$ex_p(n,H)$$ the maximum value of $$e_p(G)$$ taken over all graphs with $$n$$ vertices that do not contain $$H$$ as a subgraph. Clearly, $$ex_1(n,H)=2ex(n,H)$$ , where $$ex(n,H)$$ denotes the classical Turán number. In this paper, we consider $$ex_p(n, C_5)$$ and prove that for any positive integer $$p$$ and sufficiently large $$n$$ , there exists a constant $$c=c(p)$$ such that the following holds: if $$ex_p(n, C_5)=e_p(G)$$ for some $$C_5$$ -free graph $$G$$ of order $$n$$ , then $$G$$ is a complete bipartite graph having one vertex class of size $$cn+o(n)$$ and the other $$(1-c)n+o(n)$$ . [ABSTRACT FROM AUTHOR]

The b-chromatic index $$\varphi '(G)$$ of a graph $$G$$ is the largest integer $$k$$ such that $$G$$ admits a proper $$k$$ -edge coloring in which every color class contains at least one edge incident to some edge in all the other color classes. The b-chromatic index of trees is determined and equals either to a natural upper bound $$m'(T)$$ or one less, where $$m'(T)$$ is connected with the number of edges of high degree. Some conditions are given for which graphs have the b-chromatic index strictly less than $$m'(G)$$ , and for which conditions it is exactly $$m'(G)$$ . In the last part of the paper, regular graphs are considered. It is proved that with four exceptions, the b-chromatic index of cubic graphs is $$5$$ . The exceptions are $$K_4$$ , $$K_{3,3}$$ , the prism over $$K_3$$ , and the cube $$Q_3$$ . [ABSTRACT FROM AUTHOR]

The energy of a simple graph $$G$$ , denoted by $$E(G)$$ , is defined as the sum of the absolute values of eigenvalues of $$G$$ . In this paper, we show that, among all subdivisions of graphs with $$n$$ vertices and chromatic number $$k$$ , the subdivision of the Turán graph $$T(n,k)$$ has the maximal energy. [ABSTRACT FROM AUTHOR]

In this paper, we determine the normalization factor of photo-added squeezed vacuum state (PASVS) as a Legendre polynomial of the squeezing parameter by virtue of principle of mathematical induction, and derive the normally ordered density operator of PASVS in dissipative channel. In addition, we also give the explicit analytical expression of Husimi function in dissipative channel and study its behavior with evolution time graphically. [ABSTRACT FROM AUTHOR]

Given a graph G=( V, E) with n vertices and m edges, and a subset T of k vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most l edges (non-terminal vertices), whose removal from G separates each terminal from all the others. These two problems are NP-hard for k≥3 but well-known to be polynomial-time solvable for k=2 by the flow technique. In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in O(2 l kT( n, m)) time and Vertex Multiterminal Cut can be solved in O( k l T( n, m)) time, where T( n, m)= O(min ( n2/3, m1/2) m) is the running time of finding a minimum ( s, t) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of k: Edge 3-Terminal Cut can be solved in O(1.415 l T( n, m)) time, and Vertex {3,4,5,6}-Terminal Cuts can be solved in O(2.059 l T( n, m)), O(2.772 l T( n, m)), O(3.349 l T( n, m)) and O(3.857 l T( n, m)) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: $O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m))$ -time algorithm for Edge Multicut and O((2 k) k+ l/2 T( n, m))-time algorithm for Vertex Multicut. [ABSTRACT FROM AUTHOR]

Abstract   Given a graph and degree upper bounds on vertices, the BDMST problem requires us to find a minimum cost spanning tree respecting the given degree bounds. This problem generalizes the Travelling Salesman Path Problem (TSPP), even in unweighted graphs, and so we expect that it is necessary to relax the degree constraints to get efficient algorithms. Könemann and Ravi (Proceedings of the Thirty Second Annual ACM Symposium on Theory of Computing, pp. 537–546, 2000; Proceedings of the Thirty-Fifth ACM Symposium on Theory of Computing, pp. 389–395, 2003) give bicriteria approximation algorithms for the problem using local search techniques of Fischer (Technical Report 14853, Cornell University, 1993). Their algorithms find solutions which make a tradeoff of the approximation factor for the cost of the resulting tree against the factor by which degree constraints are violated. In particular, they give an algorithm which, for a graph with a spanning tree of cost C and degree B, and for parameters b,w>1, produces a tree whose cost is at most wC and whose degree is at most A primary contribution of Könemann and Ravi is to use a Lagrangean relaxation to formally relate the BDMST problem to what we call the MDMST problem, which is the problem of finding an MST of minimum degree in a graph. In their solution to the MDMST problem, they make central use of a local-search approximation algorithm of Fischer. In this paper, we give the first approximation algorithms for the BDMST problem—both our algorithms find trees of optimal cost. We achieve this improvement using a primal-dual cost bounding methodology from Edmonds’ weighted matching algorithms which was not previously used in this context. In order to follow Edmonds’ approach, we develop algorithms for a variant of the MDMST problem in which there are degree lower bound requirements. This variant may be of independent interest; in particular, our results extend to a generalized version of the BDMST problem in which both upper and lower degree bounds are given. First we give a polynomial-time algorithm that finds a tree of optimal cost and with maximum degree at most for any b∈(1,2). We also give a quasi-polynomial-time approximation algorithm which produces a tree of optimal cost C and maximum degree at most B+O(log n/log log n). That is, the error is additive as well as restricted just to the degree. This further improvement in degree is obtained by using augmenting-path techniques that search over a larger solution space than Fischer’s local-search algorithm. [ABSTRACT FROM AUTHOR]

For an arbitrary class of graphs $$\mathcal{G}$$ , there may not exist a function f such that $$\chi(G) \leq f(\omega(G))$$ , for every $$G \in \mathcal{G}$$ . When such a function exists, it is called a χ-binding function for $$\mathcal{G}$$ . The problem of finding an optimal χ-binding function for the class of 3 K 1-free graphs is open. In this paper, we obtain linear χ-binding function for the class of {3 K 1, H}-free graphs, where H is one of the following graphs: $$K_1 + C_4, (K_3 \cup K_1)+K_1, K_1 + P_4, K_4 \cup K_1$$ , House graph and Kite graph. We first describe structures of these graphs and then derive χ-binding functions. [ABSTRACT FROM AUTHOR]

Let G be a graph and S ⊂ V( G). We denote by α( S) the maximum number of pairwise nonadjacent vertices in S. For x, y ∈ V( G), the local connectivity κ( x, y) is defined to be the maximum number of internally-disjoint paths connecting x and y in G. We define $$\kappa(S)=\min\{\kappa(x,y) : x,y \in S,x\not=y\}$$ . In this paper, we show that if κ( S) ≥ 3 and $$\sum_{i=1}^4 d_{G}{(x_i)} \ge |V(G)|+\kappa(S)+\alpha (S)-1$$ for every independent set { x 1, x 2, x 3, x 4} ⊂ S, then G contains a cycle passing through S. This degree condition is sharp and this gives a new degree sum condition for a 3-connected graph to be hamiltonian. [ABSTRACT FROM AUTHOR]

Let G be a connected graph. For $$x, y \in V(G)$$ at distance 2, we define $$J(x, y) = \{u|u \in N(x) \cap N(y), N[u] \subseteq N[x] \cup N[y]\}$$ , and $$J^{\prime}(x, y) = \{u|u \in N (x) \cap N(y)$$ , if $$v \in N(u) \setminus (N [x] \cup N[y])$$ then $$(N(u) \cup N(x) \cup N(y)) \setminus \{x,y,v\} \subseteq N(v)\}$$ . G is quasi-claw-free $$({\mathcal{QCF}})$$ if it satisfies $$J(x, y) \neq \emptyset$$ , and G is P 3-dominated( $$\mathcal{P}_{3}{\mathcal{D}}$$ ) if it satisfies $$J(x,y)\cup J^{\prime} (x,y) \neq \emptyset$$ , for every pair ( x, y) of vertices at distance 2. Certainly $${\mathcal{P}}_3 {\mathcal{D}}$$ contains $${\mathcal{QCF}}$$ as a subclass. In this paper, we prove that the circumference of a 2-connected P 3-dominated graph G on n vertices is at least min $$\{3\delta+2,n\}$$ or $$G \in {\mathcal{F}} \cup \{K_{2,3}, K_{1,1,3}\}$$ , moreover if $$n \leq 4\delta$$ then G is hamiltonian or $$G \in {\mathcal{F}}\cup\{K_{2,3}, K_{1,1,3}\}$$ , where $${\mathcal{F}}$$ is a class of 2-connected nonhamiltonian graphs. [ABSTRACT FROM AUTHOR]

Let γ pr ( G) denote the paired domination number of graph G. A graph G with no isolated vertex is paired domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ pr ( G – v) < γ pr ( G). We call these graphs γ pr -critical. In this paper, we present a method of constructing γ pr -critical graphs from smaller ones. Moreover, we show that the diameter of a γ pr -critical graph is at most $$\frac{3}{2}(\gamma_{pr} (G)-2)$$ and the upper bound is sharp, which answers a question proposed by Henning and Mynhardt [The diameter of paired-domination vertex critical graphs, Czechoslovak Math. J., to appear]. [ABSTRACT FROM AUTHOR]

Abstract   Let T be a spanning tree of a graph G and S⊂V(G) be a set of sources. The routing cost of T is the total distance from all sources to all vertices. For an edge e of T, the swap edge of e is the edge f minimizing the routing cost of the tree formed by replacing e with f. Given an undirected graph G and a spanning tree T of G, we investigate the problem of finding the swap edge for every tree edge. In this paper, we propose an O(mlog n 2)-time algorithm for the case of two sources and an O(mn)-time algorithm for the case of more than two sources, where m and n are the numbers of edges and vertices of G, respectively. [ABSTRACT FROM AUTHOR]

This paper is dedicated to location problems on graphs. We propose a linear time algorithm for the 1-median problem on wheel graphs. Moreover, some general results for the 1-median problem are summarized and parametric median problems are investigated. These results lead to a solution method for the 2-median problem on cactus graphs, i.e., on graphs where no two cycles have more than one vertex in common. The time complexity of this algorithm is $$\mathcal O(n^2)$$ , where n is the number of vertices of the graph. [ABSTRACT FROM AUTHOR]

This paper is devoted to the search of robust solutions in finite graphs when costs depend on scenarios. We first point out similarities between robust optimization and multiobjective optimization. Then, we present axiomatic requirements for preference compatibility with the intuitive idea of robustness in a multiple scenarios decision context. This leads us to propose the Lorenz dominance rule as a basis for robustness analysis. Then, after presenting complexity results about the determination of Lorenz optima, we show how the search can be embedded in algorithms designed to enumerate k best solutions. Then, we apply it in order to enumerate Lorenz optimal spanning trees and paths. We investigate possible refinements of Lorenz dominance and we propose an axiomatic justification of OWA operators in this context. Finally, the results of numerical experiments on randomly generated graphs are provided. They show the numerical efficiency of the suggested approach. [ABSTRACT FROM AUTHOR]

In this paper, we present an exact algorithm that solves MAX-CUT in time poly(|E|) · 2|E|/4, where |E| is the number of edges (multiple edges between two vertices are allowed). This bound improves the previously known bound poly(|E|) · 2|E|/3 of Gramm et al. (2000). Bibliography: 8 titles. [ABSTRACT FROM AUTHOR]

This paper investigates the power of local computations on graphs, by considering a classical problem in distributed algorithms, the recognition problem. Formally, we want to compute some topological information on a network of processes, possibly using additional knowledge about the structure of the underlying graph. We propose the notion of recognition with structural knowledge by means of local computations. Then we characterize the graph classes that are recognizable with or without structural knowledge. The characterizations use graph coverings and a distributed enumeration algorithm proposed by A. Mazurkiewicz. Several applications are presented, in particular concerning minor-closed classes of graphs. [ABSTRACT FROM AUTHOR]