BZPEERSource author record
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
Catalog footprint
Published work
For a non-negative integer k, a vertex cut in a graph is k-degenerate if it induces a k-degenerate subgraph. We show that a graph of order n at least 2k+2 without a k-degenerate cut has the size at least 21(k+Ω(k))n and that a graph of order n at least 5 without a 2-degenerate cut has the size at least 1027n−35. For k≥2, we show that a connected graph G of order n at least k+6 and size m at most 2k+3n+2k−1 has a minimum k-degenerate cut.
Let G be a finite, simple, and undirected graph of order n and average degree d. Up to terms of smaller order, we characterize the minimal intervals I containing d that are guaranteed to contain some vertex degree. In particular, for d+∈(dn,n−1], we show the existence of a vertex in G of degree between d+−(n−d++d+2−dn(d+−d)n) and d+.
The dissociation number diss(G) of a graph G is the maximum order of a set of vertices of G inducing a subgraph that is of maximum degree at most 1. Computing the dissociation number of a given graph is algorithmically hard even when restricted to subcubic bipartite graphs. For a graph G with n vertices, m edges, k components, and c1 induced cycles of length 1 modulo 3, we show diss(G)≥n−31(m+k+c1). Furthermore, we characterize the extremal graphs in which every two cycles are vertex-disjoint.
The annihilation number a(G) of a graph G is an efficiently computable upper bound on the independence number α(G) of G. Recently, Hiller observed that a characterization of the graphs G with α(G)=a(G) due to Larson and Pepper is false. Since the known efficient algorithm recognizing these graphs was based on this characterization, the complexity of recognizing graphs G with α(G)=a(G) was once again open. We show that these graphs can indeed be recognized efficiently. More generally, we show that recognizing graphs G with α(G)≥a(G)−ℓ is fixed parameter tractable using ℓ as parameter.
We propose the notion of a majority k-edge-coloring of a graph G, which is an edge-coloring of G with k colors such that, for every vertex u of G, at most half the edges of G incident with u have the same color. We show the best possible results that every graph of minimum degree at least 2 has a majority 4-edge-coloring, and that every graph of minimum degree at least 4 has a majority 3-edge-coloring. Furthermore, we discuss a natural variation of majority edge-colorings and some related open problems.
A dissociation set in a graph is a set of vertices inducing a subgraph of maximum degree at most 1. Computing the dissociation number diss(G) of a given graph G, defined as the order of a maximum dissociation set in G, is algorithmically hard even when G is restricted to be bipartite. Recently, Hosseinian and Butenko proposed a simple 34-approximation algorithm for the dissociation number problem in bipartite graphs. Their result relies on the inequality diss(G)≤34α(G−M) implicit in their work, where G is a bipartite graph, M is a maximum matching in G, and α(G−M) denotes the independence number of G−M. We show that the pairs (G,M) for which this inequality holds with equality can be recognized efficiently, and that a maximum dissociation set can be determined for them efficiently. The dissociation number of a graph G satisfies max{α(G),2νs(G)}≤diss(G)≤α(G)+νs(G)≤2α(G), where νs(G) denotes the induced matching number of G. We show that deciding whether diss(G) equals any of the four terms lower and upper bounding diss(G) is NP-hard.
The independence number α(G) and the dissociation number diss(G) of a graph G are the largest orders of induced subgraphs of G of maximum degree at most 0 and at most 1, respectively. We consider possible improvements of the obvious inequality 2α(G)≥diss(G). For connected cubic graphs G distinct from K4, we show 5α(G)≥3diss(G), and describe the rich and interesting structure of the extremal graphs in detail. For bipartite graphs, and, more generally, triangle-free graphs, we also obtain improvements. For subcubic graphs though, the inequality cannot be improved in general, and we characterize all extremal subcubic graphs.
For a fixed positive ε, we show the existence of a constant Cε with the following property: Given a ±1-edge-labeling c:E(Kn)→{−1,1} of the complete graph Kn with c(E(Kn))=0, and a spanning forest F of Kn of maximum degree Δ, one can determine in polynomial time an isomorphic copy F′ of F in Kn with ∣c(E(F′))∣≤(43+ε)Δ+Cε. Our approach is based on the method of conditional expectation.
For a graph G, and two distinct vertices u and v of G, let nG(u,v) be the number of vertices of G that are closer in G to u than to v. Miklavič and Šparl (arXiv:2011.01635v1) define the distance-unbalancedness uB(G) of G as the sum of ∣nG(u,v)−nG(v,u)∣ over all unordered pairs of distinct vertices u and v of G. For positive integers n up to 15, they determine the trees T of fixed order n with the smallest and the largest values of uB(T), respectively. While the smallest value is achieved by the star K1,n−1 for these n, which we then proved for general n (Minimum distance-unbalancedness of trees, Journal of Mathematical Chemistry, DOI 10.1007/s10910-021-01228-4), the structure of the trees maximizing the distance-unbalancedness remained unclear. For n up to 15 at least, all these trees were subdivided stars. Contributing to problems posed by Miklavič and Šparl, we show $$\max\Big\{{\rm uB}(T):T\mbox{ is a tree of order }n\Big\} =\frac{n^3}{2}+o(n^3)$$ and max{uB(S(n1,…,nk)):1+n1+⋯+nk=n}=(21−6k5+3k21)n3+O(kn2), where S(n1,…,nk) is the subdivided star such that removing its center vertex leaves paths of orders n1,…,nk.
For a complete graph Kn of order n, an edge-labeling c:E(Kn)→{−1,1} satisfying c(E(Kn))=0, and a spanning forest F of Kn, we consider the problem to minimize ∣c(E(F′))∣ over all isomorphic copies F′ of F in Kn. In particular, we ask under which additional conditions there is a zero-sum copy, that is, a copy F′ of F with c(E(F′))=0. We show that there is always a copy F′ of F with ∣c(E(F′))∣≤Δ(F)+1, where Δ(F) is the maximum degree of F. We conjecture that this bound can be improved to ∣c(E(F′))∣≤(Δ(F)−1)/2 and verify this for F being the star K1,n−1. Under some simple necessary divisibility conditions, we show the existence of a zero-sum P3-factor, and, for sufficiently large n, also of a zero-sum P4-factor.
A matching M in a graph G is acyclic if the subgraph of G induced by the set of vertices that are incident to an edge in M is a forest. We prove that every graph with n vertices, maximum degree at most Δ, and no isolated vertex, has an acyclic matching of size at least (1−o(1))Δ26n, and we explain how to find such an acyclic matching in polynomial time.
The tree breadth tb(G) of a connected graph G is the smallest non-negative integer ρ such that G has a tree decomposition whose bags all have radius at most ρ. We show that, given a connected graph G of order n and size m, one can construct in time O(mlogn) an additive tree O(tb(G)logn)-spanner of G, that is, a spanning subtree T of G in which dT(u,v)≤dG(u,v)+O(tb(G)logn) for every two vertices u and v of G. This improves earlier results of Dragan and Köhler (Algorithmica 69 (2014) 884-905), who obtained a multiplicative error of the same order, and of Dragan and Abu-Ata (Theoretical Computer Science 547 (2014) 1-17), who achieved the same additive error with a collection of O(logn) trees.
A bihole in a bipartite graph G with partite sets A and B is an independent set I in G with ∣I∩A∣=∣I∩B∣. We prove lower bounds on the largest order of biholes in balanced bipartite graphs subject to conditions involving the vertex degrees and the average degree.
For a graph G, two dominating sets D and D′ in G, and a non-negative integer k, the set D is said to k-transform to D′ if there is a sequence D0,…,Dℓ of dominating sets in G such that D=D0, D′=Dℓ, ∣Di∣≤k for every i∈{0,1,…,ℓ}, and Di arises from Di−1 by adding or removing one vertex for every i∈{1,…,ℓ}. We prove that there is some positive constant c and there are toroidal graphs G of arbitrarily large order n, and two minimum dominating sets D and D′ in G such that D k-transforms to D′ only if k≥max{∣D∣,∣D′∣}+cn. Conversely, for every hereditary class G that has balanced separators of order n↦nα for some α<1, we prove that there is some positive constant C such that, if G is a graph in G of order n, and D and D′ are two dominating sets in G, then D k-transforms to D′ for k=max{∣D∣,∣D′∣}+⌊Cnα⌋.
Motivated by a graph theoretic process intended to measure the speed of the spread of contagion in a graph, Bonato, Janssen, and Roshanbin [Burning a Graph as a Model of Social Contagion, Lecture Notes in Computer Science 8882 (2014) 13-22] define the burning number b(G) of a graph G as the smallest integer k for which there are vertices x1,…,xk such that for every vertex u of G, there is some i∈{1,…,k} with distG(u,xi)≤k−i, and distG(xi,xj)≥j−i for every i,j∈{1,…,k}. For a connected graph G of order n, they prove that b(G)≤2⌈n⌉−1, and conjecture b(G)≤⌈n⌉. We show that b(G)≤1932⋅1−εn+19ε27 and b(G)≤712n+3≈1.309n+3 for every connected graph G of order n and every 0<ε<1. For a tree T of order n with n2 vertices of degree 2, and n≥3 vertices of degree at least 3, we show b(T)≤⌈(n+n2)+41+21⌉ and b(T)≤⌈n⌉+n≥3. Furthermore, we characterize the binary trees of depth r that have burning number r+1.
Let G be a graph, and let ρ∈(0,1). For a set D of vertices of G, let the set Hρ(D) arise by starting with the set D, and iteratively adding further vertices u to the current set if they have at least ⌈ρdG(u)⌉ neighbors in it. If Hρ(D) contains all vertices of G, then D is known as an irreversible dynamic monopoly or a perfect target set associated with the threshold function u↦⌈ρdG(u)⌉. Let hρ(G) be the minimum cardinality of such an irreversible dynamic monopoly. For a connected graph G of maximum degree at least ρ1, Chang (Triggering cascades on undirected connected graphs, Information Processing Letters 111 (2011) 973-978) showed hρ(G)≤5.83ρn(G), which was improved by Chang and Lyuu (Triggering cascades on strongly connected directed graphs, Theoretical Computer Science 593 (2015) 62-69) to hρ(G)≤4.92ρn(G). We show that for every ε>0, there is some ρ(ε)>0 such that hρ(G)≤(2+ε)ρn(G) for every ρ in (0,ρ(ε)), and every connected graph G that has maximum degree at least ρ1 and girth at least 5. Furthermore, we show that hρ(T)≤ρn(T) for every ρ in (0,1], and every tree T that has order at least ρ1.
For a set S of vertices of a graph G, a vertex u in V(G)∖S, and a vertex v in S, let dist(G,S)(u,v) be the distance of u and v in the graph G−(S∖{v}). Dankelmann et al. (Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883) define S to be an exponential dominating set of G if w(G,S)(u)≥1 for every vertex u in V(G)∖S, where w(G,S)(u)=v∈S∑(21)dist(G,S)(u,v)−1. Inspired by this notion, we define S to be an exponential independent set of G if w(G,S∖{u})(u)<1 for every vertex u in S, and the exponential independence number αe(G) of G as the maximum order of an exponential independent set of G. Similarly as for exponential domination, the non-local nature of exponential independence leads to many interesting effects and challenges. Our results comprise exact values for special graphs as well as tight bounds and the corresponding extremal graphs. Furthermore, we characterize all graphs G for which αe(H) equals the independence number α(H) for every induced subgraph H of G, and we give an explicit characterization of all trees T with αe(T)=α(T).
For a degree sequence d:d1≥⋯≥dn, we consider the smallest chromatic number χmin(d) and the largest chromatic number χmax(d) among all graphs with degree sequence d. We show that if dn≥1, then χmin(d)≤max{3,d1−4d1n+1+4}, and, if n+41−21>d1≥dn≥1, then χmax(d)=i∈[n]maxmin{i,di+1}. For a given degree sequence d with bounded entries, we show that χmin(d), χmax(d), and also the smallest independence number αmin(d) among all graphs with degree sequence d, can be determined in polynomial time.
We characterize a large subclass of the class of those graphs G for which the exponential domination number of H equals the domination number of H for every induced subgraph H of G.
A prominent parameter in the context of network analysis, originally proposed by Watts and Strogatz (Collective dynamics of `small-world' networks, Nature 393 (1998) 440-442), is the clustering coefficient of a graph G. It is defined as the arithmetic mean of the clustering coefficients of its vertices, where the clustering coefficient of a vertex u of G is the relative density m(G[NG(u)])/(2dG(u)) of its neighborhood if dG(u) is at least 2, and 0 otherwise. It is unknown which graphs maximize the clustering coefficient among all connected graphs of given order and size. We determine the maximum clustering coefficients among all connected regular graphs of a given order, as well as among all connected subcubic graphs of a given order. In both cases, we characterize all extremal graphs. Furthermore, we determine the maximum increase of the clustering coefficient caused by adding a single edge.
The domination number γ(G) of a graph G, its exponential domination number γe(G), and its porous exponential domination number γe∗(G) satisfy γe∗(G)≤γe(G)≤γ(G). We contribute results about the gaps in these inequalities as well as the graphs for which some of the inequalities hold with equality. Relaxing the natural integer linear program whose optimum value is γe∗(G), we are led to the definition of the fractional porous exponential domination number γe,f∗(G) of a graph G. For a subcubic tree T of order n, we show γe,f∗(T)=6n+2 and γe(T)≤2γe,f∗(T). We characterize the two classes of subcubic trees T with γe(T)=γe,f∗(T) and γ(T)=γe(T), respectively. Using linear programming arguments, we establish several lower bounds on the fractional porous exponential domination number in more general settings.
A set Z of vertices of a graph G is a zero forcing set of G if initially labeling all vertices in Z with 1 and all remaining vertices of G with 0, and then, iteratively and as long as possible, changing the label of some vertex u from 0 to 1 if u is the only neighbor with label 0 of some vertex with label 1, results in the entire vertex set of G. The zero forcing number Z(G), defined as the minimum order of a zero forcing set of G, was proposed as an upper bound of the corank of matrices associated with G, and was also considered in connection with quantum physics and logic circuits. In view of the computational hardness of the zero forcing number, upper and lower bounds are of interest. Refining results of Amos, Caro, Davila, and Pepper, we show that Z(G)≤Δ−1Δ−2n for a connected graph G of order n and maximum degree Δ at least 3 if and only if G does not belong to {KΔ+1,KΔ,Δ,KΔ−1,Δ,G1,G2}, where G1 and G2 are two specific graphs of orders 5 and 7, respectively. For a connected graph G of order n, maximum degree 3, and girth at least 5, we show Z(G)≤2n−Ω(lognn). Using a probabilistic argument, we show Z(G)≤(1−rHr+o(rHr))n for an r-regular graph G of order n and girth at least 5, where Hr is the r-th harmonic number. Finally, we show Z(G)≥(g−2)(δ−2)+2 for a graph G of girth g∈{5,6} and minimum degree δ, which partially confirms a conjecture of Davila and Kenter.
Let G be a graph with degree sequence d1≥…≥dn. Slater proposed sℓ(G)=min{s:(d1+1)+⋯+(ds+1)≥n} as a lower bound on the domination number γ(G) of G. We show that deciding the equality of γ(G) and sℓ(G) for a given graph G is NP-complete but that one can decide efficiently whether γ(G)>sℓ(G) or γ(G)≤(⌈ln(sℓ(G)n(G))⌉+1)sℓ(G). For real numbers α and β with α≥max{0,β}, let G(α,β) be the class of non-null graphs G such that every non-null subgraph H of G has at most αn(H)−β many edges. Generalizing a result of Desormeaux, Haynes, and Henning, we show that γ(G)≤(2α+1)sℓ(G)−2β for every graph G in G(α,β) with α≤23. Furthermore, we show that γ(G)/sℓ(G) is bounded for graphs G in G(α,β) if and only if α<2. For an outerplanar graph G with sℓ(G)≥2, we show γ(G)≤6sℓ(G)−6. In analogy to sℓ(G), we propose sℓt(G)=min{s:d1+⋯+ds≥n} as a lower bound on the total domination number. Strengthening results due to Raczek as well as Chellali and Haynes, we show that sℓt(T)≥2n+2−n1 for every tree T of order n at least 2 with n1 endvertices.
A matching in a graph is uniquely restricted if no other matching covers exactly the same set of vertices. This notion was defined by Golumbic, Hirst, and Lewenstein and studied in a number of articles. Our contribution is twofold. We provide approximation algorithms for computing a uniquely restricted matching of maximum size in some bipartite graphs. In particular, we achieve a ratio of 9/5 for subcubic bipartite graphs, improving over a 2-approximation algorithm proposed by Mishra. Furthermore, we study the uniquely restricted chromatic index of a graph, defined as the minimum number of uniquely restricted matchings into which its edge set can be partitioned. We provide tight upper bounds in terms of the maximum degree and characterize all extremal graphs. Our constructive proofs yield efficient algorithms to determine the corresponding edge colorings.
For a graph G, let γr2(G) and γR(G) denote the 2-rainbow domination number and the Roman domination number, respectively. Fujita and Furuya (Difference between 2-rainbow domination and Roman domination in graphs, Discrete Applied Mathematics 161 (2013) 806-812) proved γr2(G)+γR(G)≤46n(G) for a connected graph G of order n(G) at least 3. Furthermore, they conjectured γr2(G)+γR(G)≤34n(G) for a connected graph G of minimum degree at least 2 that is distinct from C5. We characterize all extremal graphs for their inequality and prove their conjecture.
As a natural variant of domination in graphs, Dankelmann et al. [Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883] introduce exponential domination, where vertices are considered to have some dominating power that decreases exponentially with the distance, and the dominated vertices have to accumulate a sufficient amount of this power emanating from the dominating vertices. More precisely, if S is a set of vertices of a graph G, then S is an exponential dominating set of G if v∈S∑(21)dist(G,S)(u,v)−1≥1 for every vertex u in V(G)∖S, where dist(G,S)(u,v) is the distance between u∈V(G)∖S and v∈S in the graph G−(S∖{v}). The exponential domination number γe(G) of G is the minimum order of an exponential dominating set of G. Dankelmann et al. show 41(d+2)≤γe(G)≤52(n+2) for a connected graph G of order n and diameter d. We provide further bounds and in particular strengthen their upper bound. Specifically, for a connected graph G of order n, maximum degree Δ at least 3, radius r at least 1, we show \begin{eqnarray*} γ_e(G) & \geq & \left(\frac{n}{13(Δ-1)^2}\right)^{\frac{\log_2(Δ-1)+1}{\log_2^2(Δ-1)+\log_2(Δ-1)+1}},\\[3mm] γ_e(G) & \leq & 2^{2{\rm r}-2}\mbox{, and }\\[3mm] γ_e(G) & \leq & \frac{43}{108}(n+2). \end{eqnarray*}
For a maximal outerplanar graph G of order n at least 3, Matheson and Tarjan showed that G has domination number at most n/3. Similarly, for a maximal outerplanar graph G of order n at least 5, Dorfling, Hattingh, and Jonck showed, by a completely different approach, that G has total domination number at most 2n/5 unless G is isomorphic to one of two exceptional graphs of order 12. We present a unified proof of a common generalization of these two results. For every positive integer k, we specify a set Hk of graphs of order at least 4k+4 and at most 4k2−2k such that every maximal outerplanar graph G of order n at least 2k+1 that does not belong to Hk has a dominating set D of order at most ⌊2k+1kn⌋ such that every component of the subgraph G[D] of G induced by D has order at least k.
As a natural variant of domination in graphs, Dankelmann et al. [Domination with exponential decay, Discrete Math. 309 (2009) 5877-5883] introduce exponential domination, where vertices are considered to have some dominating power that decreases exponentially with the distance, and the dominated vertices have to accumulate a sufficient amount of this power emanating from the dominating vertices. More precisely, if S is a set of vertices of a graph G, then S is an exponential dominating set of G if v∈S∑(21)dist(G,S)(u,v)−1≥1 for every vertex u in V(G)∖S, where dist(G,S)(u,v) is the distance between u∈V(G)∖S and v∈S in the graph G−(S∖{v}). The exponential domination number γe(G) of G is the minimum order of an exponential dominating set of G. In the present paper we study exponential domination in subcubic graphs. Our results are as follows: If G is a connected subcubic graph of order n(G), then 6log2(n(G)+2)+4n(G)≤γe(G)≤31(n(G)+2). For every ε>0, there is some g such that γe(G)≤εn(G) for every cubic graph G of girth at least g. For every 0<α<3ln(2)2, there are infinitely many cubic graphs G with γe(G)≤ln(n(G))α3n(G). If T is a subcubic tree, then γe(T)≥61(n(T)+2). For a given subcubic tree, γe(T) can be determined in polynomial time. The minimum exponential dominating set problem is APX-hard for subcubic graphs.
A graph G has p-intersection number at most d if it is possible to assign to every vertex u of G, a subset S(u) of some ground set U with ∣U∣=d in such a way that distinct vertices u and v of G are adjacent in G if and only if ∣S(u)∩S(v)∣≥p. We show that every minimal forbidden induced subgraph for the hereditary class G(d,p) of graphs whose p-intersection number is at most d, has order at most 3⋅2d+1+1, and that the exponential dependence on d in this upper bound is necessary. For p∈{d−1,d−2}, we provide more explicit results characterizing the graphs in G(d,p) without isolated/universal vertices using forbidden induced subgraphs.
A matching M in a graph G is uniquely restricted if there is no matching M′ in G that is distinct from M but covers the same vertices as M. Solving a problem posed by Golumbic, Hirst, and Lewenstein, we characterize the graphs in which some maximum matching is uniquely restricted. Solving a problem posed by Levit and Mandrescu, we characterize the graphs in which every maximum matching is uniquely restricted. Both our characterizations lead to efficient recognition algorithms for the corresponding graphs.
We show that an identifying code of minimum order in the complementary prism of a cycle of order n has order 7n/9+Θ(1). Furthermore, we observe that the clique-width of the complementary prism of a graph of clique-width k is at most 4k, and discuss some algorithmic consequences.
The independence number α(H) of a hypergraph H is the maximum cardinality of a set of vertices of H that does not contain an edge of H. Generalizing Shearer's classical lower bound on the independence number of triangle-free graphs (J. Comb. Theory, Ser. B 53 (1991) 300-307), and considerably improving recent results of Li and Zang (SIAM J. Discrete Math. 20 (2006) 96-104) and Chishti et al. (Acta Univ. Sapientiae, Informatica 6 (2014) 132-158), we show that α(H)≥∑u∈V(H)fr(dH(u)) for an r-uniform linear triangle-free hypergraph H with r≥2, where \begin{eqnarray*} f_r(0)&=&1\mbox{, and }\\ f_r(d)&=&\frac{1+\Big((r-1)d^2-d\Big)f_r(d-1)}{1+(r-1)d^2}\mbox{ for d≥1.} \end{eqnarray*}
For a sequence d of non-negative integers, let F(d) be the set of all forests whose degree sequence is d. We present closed formulas for γmaxF(d)=max{γ(F):F∈F(d)} and αminF(d)=min{α(F):F∈F(d)} where γ(F) and α(F) are the domination number and the independence number of a forest F, respectively.
The research in the present paper was motivated by the conjecture of Ryjáček that every locally connected graph is weakly pancyclic. For a connected locally connected graph G of order at least 3, our results are as follows: If G is (K1+(K1∪K2))-free, then G is weakly pancyclic. If G is (K1+(K1∪K2))-free, then G is fully cycle extendable if and only if 2δ(G)≥n(G). If G is {K1+K1+Kˉ3,K1+P4}-free or {K1+K1+Kˉ3,K1+(K1∪P3)}-free, then G is fully cycle extendable. If G is distinct from K1+K1+Kˉ3 and {K1+P4,K1,4,K2+(K1∪K2)}-free, then G is fully cycle extendable. Furthermore, if G is a connected graph of order at least 3 such that ∣NG(u)∩NG(v)∩NG(w)∣>∣NG(u)∖(NG[v]∪NG[w])∣ for every induced path vuw of order 3 in G, then G is fully cycle extendable, which implies that every connected locally Ore or locally Dirac graph of order at least 3 is fully cycle extendable.
For a graph G, let γR(G) and γr2(G) denote the Roman domination number of G and the 2-rainbow domination number of G, respectively. It is known that γr2(G)≤γR(G)≤23γr2(G). Fujita and Furuya (Difference between 2-rainbow domination and Roman domination in graphs, Discrete Applied Mathematics 161 (2013) 806-812) present some kind of characterization of the graphs G for which γR(G)−γr2(G)=k for some integer k. Unfortunately, their result does not lead to an algorithm that allows to recognize these graphs efficiently. We show that for every fixed non-negative integer k, the recognition of the connected K4-free graphs G with γR(G)−γr2(G)=k is NP-hard, which implies that there is most likely no good characterization of these graphs. We characterize the graphs G such that γr2(H)=γR(H) for every induced subgraph H of G, and collect several properties of the graphs G with γR(G)=23γr2(G).
Addressing a problem posed by Chellali, Haynes, and Hedetniemi (Discrete Appl. Math. 178 (2014) 27-32) we prove γr2(G)≤2γr(G) for every graph G, where γr2(G) and γr(G) denote the 2-rainbow domination number and the weak Roman domination number of G, respectively. We characterize the extremal graphs for this inequality that are {K4,K4−e}-free, and show that the recognition of the K5-free extremal graphs is NP-hard.
For a sequence d of non-negative integers, let G(d) and F(d) be the sets of all graphs and forests with degree sequence d, respectively. Let γmin(d)=min{γ(G):G∈G(d)}, αmax(d)=max{α(G):G∈G(d)}, γminF(d)=min{γ(F):F∈F(d)}, and αmaxF(d)=max{α(F):F∈F(d)} where γ(G) is the domination number and α(G) is the independence number of a graph G. Adapting results of Havel and Hakimi, Rao showed in 1979 that αmax(d) can be determined in polynomial time. We establish the existence of realizations G∈G(d) with γmin(d)=γ(G), and Fγ,Fα∈F(d) with γminF(d)=γ(Fγ) and αmaxF(d)=α(Fα) that have strong structural properties. This leads to an efficient algorithm to determine γmin(d) for every given degree sequence d with bounded entries as well as closed formulas for γminF(d) and αmaxF(d).
We provide a constructive characterization of the trees for which the Roman domination number strongly equals the weak Roman domination number, that is, for which every weak Roman dominating function of minimum weight is a Roman dominating function. Our characterization is based on five simple extension operations, and reveals several structural properties of these trees.
We prove that, for every integer d with d≥3, there is an approximation algorithm for the maximum induced matching problem restricted to {C3,C5}-free d-regular graphs with performance ratio 0.7083ˉd+0.425, which answers a question posed by Dabrowski et al. (Theor. Comput. Sci. 478 (2013) 33-40). Furthermore, we show that every graph with m edges that is k-degenerate and of maximum degree at most d with k<d, has an induced matching with at least m/((3k−1)d−k(k+1)+1) edges.
For every positive integer k, we show that every graph of order n at least 3k with more than max{(22k−1)+(2k−1)(n−(2k−1)),(23k−1)+(n−(3k−1))} edges has k vertex disjoint cycles, which is a best possible density version of a theorem of Corrádi and Hajnal.
We characterize the graphs for which the independence number equals the packing number. As a consequence we obtain simple structural descriptions of the graphs for which (i) the distance-k-packing number equals the distance-2k-packing number, and (ii) the distance-k-matching number equals the distance-2k-matching number. This last result considerably simplifies and extends previous results of Cameron and Walker (The graphs with maximum induced matching and maximum matching the same size, Discrete Math. 299 (2005) 49-55). For positive integers k1 and k2 with k1<k2 and ⌈(3k2+1)/2⌉≤2k1+1, we prove that it is NP-hard to determine for a given graph whether its distance-k1-packing number equals its distance-k2-packing number.
We show that a cubic graph G of order n has an induced 2-regular subgraph of order at least a) 4−k4n−2, if G has no induced cycle of length more than k, b) 85n+6, if G has no induced cycle of length more than 4, and n>6, and c) (41+ε)n, if the independence number of G is at most (83−ε)n. To show the second result we give a precise structural description of cubic 4-chordal graphs.
The Gallai graph Γ(G) of a graph G has the edges of G as its vertices and two distinct vertices e and f of Γ(G) are adjacent in Γ(G) if the edges e and f of G are adjacent in G but do not span a triangle in G. Clearly, Γ(G) is a subgraph of the line graph of G. While line graphs can be recognized efficiently the complexity of recognizing Gallai graphs is unknown. In the present paper we characterize those graphs whose Gallai graphs are forests or trees, respectively.
We prove that a cubic graph with m edges has an induced matching with at least m/9 edges. Our result generalizes a result for planar graphs due to Kang, Mnich, and Müller (Induced matchings in subcubic planar graphs, SIAM J. Discrete Math. 26 (2012) 1383-1411) and solves a conjecture of Henning and Rautenbach (Induced matchings in subcubic graphs without short cycles, to appear in Discrete Math.).
If G is a claw-free hamiltonian graph of order n and maximum degree Δ with Δ≥24, then G has cycles of at least min{n,⌈23Δ⌉}−2 many different lengths.
Let G be a graph of order n. Let lpt(G) be the minimum cardinality of a set X of vertices of G such that X intersects every longest path of G and define lct(G) analogously for cycles instead of paths. We prove that lpt(G) \leq ceiling(n/4-n^{2/3}/90), if G is connected, lct(G) \leq ceiling(n/3-n^{2/3}/36), if G is 2-connected, and \lpt(G) \leq 3, if G is a connected circular arc graph. Our bound on lct(G) improves an earlier result of Thomassen and our bound for circular arc graphs relates to an earlier statement of Balister \emph{et al.} the argument of which contains a gap. Furthermore, we prove upper bounds on lpt(G) for planar graphs and graphs of bounded tree-width.
Let G=(V,E) be a graph. A vertex dominates itself and all its neighbors, i.e., every vertex v in V dominates its closed neighborhood N[v]. A vertex set D in G is an efficient dominating (e.d.) set for G if for every vertex v in V, there is exactly one d in D dominating v. An edge set M is an efficient edge dominating (e.e.d.) set for G if it is an efficient dominating set in the line graph L(G) of G. The ED problem (EED problem, respectively) asks for the existence of an e.d. set (e.e.d. set, respectively) in the given graph. We give a unified framework for investigating the complexity of these problems on various classes of graphs. In particular, we solve some open problems and give linear time algorithms for ED and EED on dually chordal graphs. We extend the two problems to hypergraphs and show that ED remains NP-complete on alpha-acyclic hypergraphs, and is solvable in polynomial time on hypertrees, while EED is polynomial on alpha-acyclic hypergraphs and NP-complete on hypertrees.
We provide a proof of Sholander's claim (Trees, lattices, order, and betweenness, Proc. Amer. Math. Soc. 3, 369-381 (1952)) concerning the representability of collections of so-called segments by trees, which yields a characterization of the interval function of a tree. Furthermore, we streamline Burigana's characterization (Tree representations of betweenness relations defined by intersection and inclusion, Mathematics and Social Sciences 185, 5-36 (2009)) of tree betweenness and provide a relatively short proof.
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.