Search

Abstract The fixing number of a graph Γ is the minimum number of labeled vertices that, when fixed, remove all nontrivial automorphisms from the automorphism group of Γ. The fixing set of a finite group G is the set of all fixing numbers of graphs whose automorphism groups are isomorphic to G. Previously, authors have studied the fixing sets of both abelian groups and symmetric groups. In this article, we determine the fixing set of the dihedral group. [ABSTRACT FROM AUTHOR]

The independence polynomial i ( G , x ) of a graph G is the generating function of the numbers of independent sets of each size. A graph of order n is very well-covered if every maximal independent set has size n ∕ 2 . Levit and Mandrescu conjectured that the independence polynomial of every very well-covered graph is unimodal (that is, the sequence of coefficients is nondecreasing, then nonincreasing). In this article we show that every graph is embeddable as an induced subgraph of a very well-covered graph whose independence polynomial is unimodal, by considering the location of the roots of such polynomials. [ABSTRACT FROM AUTHOR]

Graph-based semi-supervised learning (SSL), which performs well in hyperspectral image classification with a small amount of labeled samples, has drawn a lot of attention in the past few years. The key step of graph-based SSL is to construct a good graph to represent original data structures. Among the existing graph construction methods, sparse representation (SR) based methods have shown impressive performance on graph-based SSL. However, most SR based methods fail to take into consideration the class structure of data. In SSL, we can obtain a probabilistic class structure, which implies the probabilistic relationship between each sample and each class, of the whole data by utilizing a small amount of labeled samples. Such class structure information can help SR model to yield a more discriminative coefficients, which motivates us to exploit this class structure information in order to learn a discriminative graph. In this paper, we present a discriminative graph construction method called probabilistic class structure regularized sparse representation (PCSSR) approach, by incorporating the class structure information into the SR model, PCSSR can learn a discriminative graph from the data. A class structure regularization is developed to make use of the probabilistic class structure, and therefore to improve the discriminability of the graph. We formulate our problem as a constrained sparsity minimization problem and solve it by the alternating direction method with adaptive penalty (ADMAP). The experimental results on Hyperion and AVIRIS hyperspectral data show that our method outperforms state of the art. [ABSTRACT FROM AUTHOR]

The energy of a graph is defined as the sum of the absolute values of all eigenvalues of the graph. The subgraph grafting operation on a graph is a kind of subgraph moving between two vertices of the graph. In this paper, we introduce two new subgraph grafting operations on bipartite graph and show how the graph energy changes under these subgraph grafting operations. As the application of these operations, we determine the trees with the third and fourth minimal energies in the set of trees with given order and domination number. [ABSTRACT FROM AUTHOR]

In 1930s Hassler Whitney considered and completely solved the problem ( W P ) of describing the classes of graphs G having the same cycle matroid M ( G ) (Whitney, 1933; Whitney, 1932). A natural analog ( W P ) ′ of Whitney’s problem ( W P ) is to describe the classes of graphs G having the same matroid M ′ ( G ) , where M ′ ( G ) is a matroid (on the edge set of G ) distinct from M ( G ) . For example, the corresponding problem ( W P ) ′ = ( W P ) θ for the so-called bicircular matroid M θ ( G ) of graph G was solved in Coulard et al. (1991) and Wagner (1985). In De Jesús and Kelmans (2015) we introduced and studied the so-called k -circular matroids M k ( G ) for every non-negative integer k that is a natural generalization of the cycle matroid M ( G ) : = M 0 ( G ) and of the bicircular matroid M θ ( G ) : = M 1 ( G ) of graph G . In this paper (which is a continuation of our paper De Jesús and Kelmans (2015)) we establish some properties of graphs guaranteeing that the graphs are uniquely defined by their k -circular matroids. [ABSTRACT FROM AUTHOR]

Let G be a graph of order n . A dominating set of G is a subset of vertices of G , say S , such that every vertex in V ( G ) ∖ S is adjacent to at least one vertex of S . The domination polynomial of G is the polynomial D ( G , x ) = ∑ i = 1 n d ( G , i ) x i , where d ( G , i ) is the number of dominating sets of G of size i . A root of D ( G , x ) is called a domination root of G . Let δ = δ ( G ) be the minimum degree of vertices of G . We prove that all roots of D ( G , x ) lies in the set { z : | z + 1 | ≤ 2 n − 1 δ + 1 } . We show that D ( G , x ) has at least δ − 1 non-real roots. In particular, we prove that if all roots of D ( G , x ) are real, then δ = 1 . We construct an infinite family of graphs such that all roots of their polynomials are real. Motivated by a conjecture (Akbari, et al. 2010) which states that every integer root of D ( G , x ) is − 2 or 0, we prove that if δ ≥ 2 n 3 − 1 , then every integer root of D ( G , x ) is − 2 or 0. Also we prove that the conjecture is valid for trees and unicyclic graphs. Finally we characterize all graphs that their domination roots are integer. [ABSTRACT FROM AUTHOR]

By resorting to a new matrix product, called semi-tensor product of matrices, this paper investigates the minimum stable set and core of graph, and also presents a number of results and algorithms. By defining a characteristic logical vector and using matrix expressions of logical functions, a new algebraic representation is derived for the externally stable set. Then, based on the algebraic representation, an algorithm is established to find all the externally stable sets. According to this algorithm, a new necessary and sufficient condition is obtained to determine whether a given vertex subset is an absolutely minimum externally stable set or not. Meanwhile, a new algorithm is also obtained to find all the absolutely minimum externally stable sets. Finally, the graph core, which is simultaneously externally stable set and internally stable set, is investigated. Here the internally stable set requires that internal nodes of this set are all disconnected with each other. Using semi-tensor product, some necessary and sufficient conditions are presented, and then an algorithm is established to find all the graph cores. The study of illustrative examples shows that the results/algorithms presented in this paper are effective. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

This paper addresses the task of time-separated aerial image registration. The ability to solve this problem accurately and reliably is important for a variety of subsequent image understanding applications. The principal challenge lies in the extent and nature of transient appearance variation that a land area can undergo, such as that caused by the change under illumination conditions, seasonal variations, or the occlusion by non-persistent objects (people, cars). Our work introduces several major novelties (i) unlike previous work on aerial image registration, we approach the problem using a set-based paradigm; (ii) we show how image space local, pair-wise constraints can be used to enforce a globally good registration using a constraints graph structure; (iii) we show how a simple holistic representation derived from raw aerial images can be used as a basic building block of the constraints graph in a manner which achieves both high registration accuracy and speed; (iv) lastly, we introduce a new and, to the best of our knowledge, the only data corpus suitable for the evaluation of set-based aerial image registration algorithms. Using this data set, we demonstrate (i) that the proposed method outperforms the state-of-the-art for pair-wise registration already, achieving greater accuracy and reliability, while at the same time reducing the computational cost of the task and (ii) that the increase in the number of available images in a set consistently reduces the average registration error, with a major difference already for a single additional image. [ABSTRACT FROM AUTHOR]

A theorem of Ore [20] states that if D is a minimal dominating set in a graph G = ( V , E ) having no isolated nodes, then V − D is a dominating set. It follows that such graphs must have two disjoint minimal dominating sets R and B . We describe a self-stabilizing algorithm for finding such a pair of sets. It also follows from Ore's theorem that in a graph with no isolates, one can find disjoint sets R and B where R is maximal independent and B is minimal dominating. We describe a self-stabilizing algorithm for finding such a pair. Both algorithms are described using the Distance-2 model, but can be converted to the usual Distance-1 model [7] , yielding running times of O ( n 2 m ) . [ABSTRACT FROM AUTHOR]

A signed graph is a pair ( G , Σ ) , where G = ( V , E ) is a graph (in which parallel edges and loops are permitted) with V = { 1 , … , n } and Σ ⊆ E . The edges in Σ are called odd edges and the other edges of E even. By S ( G , Σ ) we denote the set of all symmetric n × n real matrices A = [ a i , j ] such that if a i , j < 0 , then among the edges connecting i and j , there must be at least one even edge; if a i , j > 0 , then among the edges connecting i and j , there must be at least one odd edge; and if a i , j = 0 , then either there must be at least one odd edge and at least one even edge connecting i and j , or there are no edges connecting i and j . (Here we allow i = j .) For a symmetric real matrix A , the partial inertia of A is the pair ( p , q ) , where p and q are the numbers of positive and negative eigenvalues of A , respectively. If ( G , Σ ) is a signed graph, we define the inertia set of ( G , Σ ) as the set of the partial inertias of all matrices A ∈ S ( G , Σ ) . In this paper, we present formulas that allows us to obtain the minimal elements of the inertia set of ( G , Σ ) in case ( G , Σ ) has a 1-separation using the inertia sets of certain signed graphs associated with the 1-separation. [ABSTRACT FROM AUTHOR]

A 1989 result of Duarte asserts that for a given tree T on n vertices, a fixed vertex i , and two sets of distinct real numbers L , M of sizes n and n − 1 , respectively, such that M strictly interlaces L , there is a real symmetric matrix A such that graph of A is T , eigenvalues of A are given by L , and eigenvalues of A ( i ) are given by M . In 2013, a similar result for connected graphs was published by Hassani Monfared and Shader, using the Jacobian method. Analogues of these results are presented here for real skew-symmetric matrices whose graphs belong to a certain family of trees, and all of their supergraphs. [ABSTRACT FROM AUTHOR]

For a connected graph G = ( V , E ) , an edge set S ⊆ E ( G ) is called a k -restricted edge cut of G if G − S is disconnected and every component of G − S has at least k vertices. The k -restricted edge connectivity of G , denoted by λ k ( G ) , is defined as the cardinality of a minimum k -restricted edge cut. For two disjoint vertex subsets X , Y of G , define [ X , Y ] = { x y ∈ E ( G ) : x ∈ X , y ∈ Y } and define ξ k ( G ) = min { | [ X , X ¯ ] | : X ⊆ V ( G ) , | X | = k , G [ X ] is connected } , where X ¯ = V ( G ) ∖ X . G is λ k -optimal if λ k ( G ) = ξ k ( G ) . Furthermore, G is super- λ k if every minimum k -restricted edge cut of G isolates a connected subgraph with order k . The k -restricted edge connectivity is an important index to estimate the reliability of networks. In this paper, some degree conditions for graphs to be maximally k -restricted edge connected and super k -restricted edge connected are given. [ABSTRACT FROM AUTHOR]

This study examines the notion of generators of a pairwise comparisons matrix. Such approach decreases the number of pairwise comparisons from n · ( n - 1 ) to n - 1 . An algorithm of reconstructing of the PC matrix from its set of generators is presented. [ABSTRACT FROM AUTHOR]

Let G be a graph with vertex set V(G) and edge set E(G). An edge subset S ⊆ E(G) is called a k-restricted edge cut if G − S is not connected and every component of G − S has at least k vertices. The k-restricted edge connectivity of a connected graph G, denoted by λk (G), is defined as the cardinality of a minimum k-restricted edge cut. Let [X, &Xmacr;] denote the set of edges between a vertex set X ⊂ V(G) and its complement &Xmacr; = V(G)\X. A vertex set X ⊂ V (G) is called a λk-fragment if [X, &Xmacr;] is a minimum k-restricted edge cut of G. Letξk(G) = min{|[X, &Xmacr;]|:|X| = k, G [X ] is connected}. In this work, we give a lower bound on the cardinality of λk-fragments of a graph G satisfying λk (G) < ξk (G) and containing no (p + 1) -cliques. As a consequence of this result, we show a sufficient condition for a graph G with λk (G) = ξk(G). [ABSTRACT FROM AUTHOR]

Judicious Partition Problem is to partition the vertex set of a graph such that certain quantities are optimized simultaneously. Let k be a positive integer and G a graph with m edges. It is proved in this paper that the vertex set of G can be partitioned into k parts V 1 , … , V k such that e ( V i ) ≤ m k 2 + k − 1 2 k 2 ( 2 m + 1 4 − 1 2 ) + 2 3 for each i ∈ { 1 , 2 , … , k } and e ( V 1 , … , V k ) ≥ k − 1 k m + k − 1 2 k ( 2 m + 1 4 − 1 2 ) − ( k − 2 ) 2 8 k , where e ( V i ) is the number of edges with both ends in V i and e ( V 1 , … , V k ) = m − ∑ i = 1 k e ( V i ) . This partially solves a problem proposed by Bollobás and Scott, and, for some values of m , solves the problem affirmatively. [ABSTRACT FROM AUTHOR]

For a graph G = ( V , E ) with V = { 1 , 2 , … , n } , let S ( G ) be the set of all symmetric real n × n matrices A = [ a i , j ] with a i , j ≠ 0 , i ≠ j if and only if i j ∈ E . The inertia set of a graph G is the set of all possible inertias of matrices in S ( G ) . In this paper we give a formula that expresses the inertia set of a graph with a 2-separation in terms of the inertia sets of subgraphs of G . This formula follows from an extension to arbitrary fields with characteristic not equal to two. [ABSTRACT FROM AUTHOR]

Let G be a simple graph of order n with vertex set V = { v 1 , v 2 , … , v n } . Also let μ 1 ( G ) ≥ μ 2 ( G ) ≥ ⋯ ≥ μ n − 1 ( G ) ≥ μ n ( G ) = 0 and q 1 ( G ) ≥ q 2 ( G ) ≥ ⋯ ≥ q n ( G ) ≥ 0 be the Laplacian eigenvalues and signless Laplacian eigenvalues of G , respectively. In this paper we obtain μ i ( G ) ≤ i − 1 + min U i ⁡ max ⁡ { | N H ( v k ) ∪ N H ( v j ) | : v k v j ∈ E ( H ) } , where N H ( v k ) is the set of neighbors of vertex v k in V ( H ) = V ( G ) \ U i , U i is any ( i − 1 ) -subset of V ( G ) (here, we agree that i ∈ { 1 , … , n − 1 } and μ i ( G ) ≤ i − 1 if E ( H ) = ∅ ). For any graph G , this bound does not exceed the order of G . Moreover, we prove that max ⁡ { μ i ( G ) , q i ( G ) } ≤ max i ≤ k ≤ n ⁡ { d G ( v k ) + ∑ v j ∈ N G ( v k ) ∩ N d G ( v j ) d G ( v k ) } ≤ 2 d G ( v i ) , where d G ( v i ) is the i -th largest degree of G and N = { v i , v i + 1 , … , v n } . [ABSTRACT FROM AUTHOR]

Abstract: Let be the set of matrices over a field . Consider a graph with as the vertex set such that two vertices are adjacent if . We study graph properties of G when is a finite field. In particular, G is a regular connected graph with diameter equal to ; it is always Hamiltonian. Furthermore, we determine the independence number, chromatic number and clique number of G. These results are used to characterize the graph endomorphisms of G, which extends Hua's fundamental theorem of geometry on . [Copyright &y& Elsevier]

Abstract: A graph is arbitrarily partitionable if for any sequence of positive integers adding up to , there is a sequence of vertex-disjoint subsets of whose orders are given by , and which induce connected subgraphs. Such a graph models, e.g., a computer network which may be arbitrarily partitioned into connected subnetworks. In this paper we study the structure of such graphs and prove that unlike in some related problems, arbitrarily partitionable graphs may have arbitrarily many components after removing a cutset of a given size . The sizes of these components grow exponentially, though. [Copyright &y& Elsevier]

Abstract: Let be a simple graph with vertex set and edge set . The Laplacian matrix of G is , where is the diagonal matrix of its vertex degrees and is the adjacency matrix. Let be the Laplacian eigenvalues of G. For a graph G and a real number , the graph invariant is the sum of the β-th power of the non-zero Laplacian eigenvalues of G, that is, In this paper, we obtain some lower and upper bounds on for G in terms of n, the number of edges m, maximum degree , clique number ω, independence number α and the number of spanning trees t. Moreover, we present some Nordhaus–Gaddum-type results for of G. [Copyright &y& Elsevier]

Abstract: Assume that is an undirected graph with vertex set and edge set . The ball denotes the vertices within graphical distance from . A subset is called an -locating–dominating code of type B if the sets are distinct for all subsets with at most vertices. We give examples of optimal -locating–dominating codes of type in the infinite king grid for all and prove optimality. The infinite king grid is the graph with vertex set and edge set . [Copyright &y& Elsevier]

Abstract: Let be a simple connected graph with vertex set and edge set . The first Zagreb index and the second Zagreb index are defined as follows: and where is the degree of vertex in . The eccentric connectivity index of a graph , denoted by , is defined as where is the eccentricity of in . Recently, Das and Trinajstić (2011) [11] compared the eccentric connectivity index and Zagreb indices for chemical trees and molecular graphs. However, the comparison between the eccentric connectivity index and Zagreb indices, in the case of general trees and general graphs, is very hard and remains unsolved till now. In this paper, we compare the eccentric connectivity index and Zagreb indices for some graph families. We first give some sufficient conditions for a graph satisfying , . Then we introduce two classes of composite graphs, each of which has larger eccentric connectivity index than the first Zagreb index, if the original graph has larger eccentric connectivity index than the first Zagreb index. As a consequence, we can construct infinite classes of graphs having larger eccentric connectivity index than the first Zagreb index. [Copyright &y& Elsevier]

Abstract: The n-th Fiedler value of a class of graphs is the maximum second eigenvalue of a graph with n vertices. In this note we relate this value to shallow minors and, as a corollary, we determine the right order of the n-th Fiedler value for some minor closed classes of graphs, including the class of planar graphs. [Copyright &y& Elsevier]

Abstract: The positive semidefinite zero forcing number of a graph G was introduced in Barioli et al. (2010) [4]. We establish a variety of properties of : Any vertex of G can be in a minimum positive semidefinite zero forcing set (this is not true for standard zero forcing). The graph parameters (tree-width), , and (standard zero forcing number) all satisfy the Graph Complement Conjecture (see Barioli et al. (2012) [3]). Graphs having extreme values of the positive semidefinite zero forcing number are characterized. The effect of various graph operations on positive semidefinite zero forcing number and connections with other graph parameters are studied. [Copyright &y& Elsevier]

Abstract: A signed graph is a pair , where is a graph (in which parallel edges are permitted, but loops are not) with and . The edges in are called odd edges and the other edges of E even. By we denote the set of all symmetric matrices with if i and j are adjacent and all edges between i and j are even, if i and j are adjacent and all edges between i and j are odd, if i and j are connected by even and odd edges, if and i and j are non-adjacent, and for all vertices i. The stable inertia set of a signed graph is the set of all pairs for which there exists a matrix with p positive and q negative eigenvalues which has the Strong Arnold Property. In this paper, we study the stable inertia set of (signed) graphs. [Copyright &y& Elsevier]

Abstract: In this paper we deal with cover–incomparability graphs of posets, or briefly C–I graphs. These are graphs derived from posets as the edge-union of their cover graph and their incomparability graph. We answer two recently posed open questions. Which distance-hereditary graphs are C–I graphs? Which Ptolemaic (i.e. chordal distance-hereditary) graphs are C–I graphs? It follows that C–I graphs can be recognized efficiently in the class of all distance-hereditary graph whereas recognizing C–I graphs in general is known to be NP-complete. [Copyright &y& Elsevier]

Abstract: We introduce a Laplacian and a signless Laplacian for the distance matrix of a connected graph, called the distance Laplacian and distance signless Laplacian, respectively. We show the equivalence between the distance signless Laplacian, distance Laplacian and the distance spectra for the class of transmission regular graphs. There is also an equivalence between the Laplacian spectrum and the distance Laplacian spectrum of any connected graph of diameter 2. Similarities between n, as a distance Laplacian eigenvalue, and the algebraic connectivity are established. [Copyright &y& Elsevier]

Abstract: Let be a simple graph with vertex set and edge set . The Laplacian matrix of G is , where is the diagonal matrix of its vertex degrees and is the adjacency matrix. Among all eigenvalues of the Laplacian matrix of a graph, the most studied is the second smallest, called the algebraic connectivity of a graph [18]. In this paper we give a lower bound on the algebraic connectivity of graphs. Moreover, we mention two conjectures, obtained by the system AutoGraphiX, about the algebraic connectivity , diameter and the minimum degree of graphs (see, [2], available online at http://www.gerad.ca/∼agx/):with equality if and only if G is isomorphic to a graph with and , and (ii) is minimum for a graph composed of 2 cliques on vertices with a common vertex if n is odd, and linked by an edge if n is even. Here we prove conjecture in (i) using the lower bound on the algebraic connectivity of graphs and conjecture in (ii), respectively. [Copyright &y& Elsevier]

Abstract: Let be a connected graph with vertex set and a weight function that assigns a nonnegative number to each of its vertices. Then, the -moment of at vertex is defined to be , where stands for the distance function. Adding up all these numbers, we obtain the -moment of : This parameter generalizes, or it is closely related to, some well-known graph invariants, such as the Wiener index , when for every , and the degree distance , obtained when , the degree of vertex . In this paper we derive some exact formulas for computing the -moment of a graph obtained by a general operation called graft product, which can be seen as a generalization of the hierarchical product, in terms of the corresponding -moments of its factors. As a consequence, we provide a method for obtaining nonisomorphic graphs with the same -moment for every (and hence with equal mean distance, Wiener index, degree distance, etc.). In the case when the factors are trees and/or cycles, techniques from linear algebra allow us to give formulas for the degree distance of their product. [Copyright &y& Elsevier]

Abstract: Let be a graph. A set is a restrained dominating set if every vertex in is adjacent to a vertex in and to a vertex in . The restrained domination number of , denoted by , is the smallest cardinality of a restrained dominating set of . In this paper we will bound the size of a graph , given the restrained domination number of . [Copyright &y& Elsevier]

Abstract: The power of a graph , denoted by , is the graph with the same vertex set as , such that two vertices are adjacent in if and only if their distance is at most in . In this paper, we give bounds on the first two largest Laplacian eigenvalues of the second power of a general graph, and on the second power of a tree. We also give a Nordhaus–Gaddum-type inequality for the Laplacian spectral radius of . [Copyright &y& Elsevier]

Abstract: The exact crossing number is known only for a few specific families of graphs. Cartesian products of two graphs belong to the first families of graphs for which the crossing number has been studied. Let be a path with vertices. , the -power of the graph , is a graph on the same vertex set as and the edges that join two vertices of if the distance between them is at most . Very recently, some results concerning crossing numbers of were obtained. In this paper, the crossing numbers of the Cartesian product of with the cycle are studied. It is proved that the crossing number of the graph is , and the upper bound for the crossing number of the graph is given. [Copyright &y& Elsevier]

Abstract: Let be a graph and be the set of with all of its neighbors in . A set of vertices is called an identifying code of if, for every pair of distinct vertices and , both and are nonempty and distinct. A minimum identifying code of a graph is an identifying code of with minimum cardinality and is the cardinality of a minimum identifying code for . A minimum identifying code graph of order is a graph with having the minimum number of edges. Moncel (2006) constructed minimum identifying code graphs of order for and left the same problem but for arbitrary order open. In this paper, we aimed at the construction of connected minimum identifying code graphs in order to solve this problem for integer order greater than or equal to 4. Furthermore, we discussed some related properties. [Copyright &y& Elsevier]

Abstract: Let denote the undirected path of length . The cardinality of the set of congruence classes induced by the graph homomorphisms from onto is determined. This settles an open problem of Michels and Knauer [M. A. Michels, U. Knauer, The congruence classes of paths and cycles, Discrete Mathematics, 309 (2009) 5352–5359]. Our result is based on a new proven formula of the number of homomorphisms between paths. [Copyright &y& Elsevier]

Abstract: Let be a graph. A global secure set is a dominating set which also satisfies a condition that for every subset . The minimum cardinality of the global secure set in the graph is denoted by . In this paper, we introduce the notion of -monotone graphs. The graph is -monotone if, for every , it has a global secure set of cardinality . We will also present the results concerning the minimum cardinality of the global secure sets in the class of cographs. [Copyright &y& Elsevier]

Abstract: Consider the following generalization of the sequential group testing problem for 2 defective items, which is suggested by Aigner (1988) in : Suppose a graph contains one defective edge . Find the endpoints of by testing whether a subset of vertices of cardinality at most 2 contains at least one of the endpoints of or not. What is then the minimum number of tests, which are needed in the worst case to identify ? In Gerzen (2009) , this problem was partially solved by deriving sharp lower and upper bounds for . In addition, it was proved that the determination of is an NP-complete problem. Among others, it was shown that the inequality holds for graphs with 2-complexity and the edge set . In the present paper, we study the class of graphs for which this inequality is sharp and characterize these graphs in several ways. We suppose that for those graphs the 2-complexity can be computed in polynomial time by means of this characterization. [Copyright &y& Elsevier]

Abstract: Given a metric continuum X, let and denote the hyperspaces of all nonempty closed subsets and subcontinua, respectively. For we say that B does not block A if and the union of all subcontinua of X intersecting A and contained in is dense in X. In this paper we study some sets of blockers for several kinds of continua. In particular, we determine their Borel classes and, for a large class of locally connected continua X, we recognize them as cap-sets. [Copyright &y& Elsevier]

Abstract: Let be a simple graph with vertex set and edge set . The adjacency matrix of a graph is denoted by and defined as the matrix , where for and 0 otherwise. The largest eigenvalue () of is called the spectral radius or the index of . The Laplacian matrix of is , where is the diagonal matrix of its vertex degrees and is the adjacency matrix. Among all eigenvalues of the Laplacian matrix of a graph, the most studied is the second smallest, called the algebraic connectivity () of a graph [12]. In [1,2], Aouchiche et al. have given a series of conjectures on index () and algebraic connectivity () of (see also [3]). Here we prove two conjectures and disprove one by a counter example. [Copyright &y& Elsevier]

Abstract: The nullity of a graph is defined as the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. We investigate a class of graphs with pendant trees, and express the nullity of such graph in terms of that of its subgraphs. As an application of our results, we characterize unicyclic graphs with a given nullity. [ABSTRACT FROM AUTHOR]

Abstract: Generalised Sierpiński carpets are planar sets that generalise the well-known Sierpiński carpet and are defined by means of sequences of patterns. We present necessary and sufficient conditions, under which generalised Sierpiński carpets are connected, with respect to Euclidean topology. [Copyright &y& Elsevier]

Abstract: A discrete dynamical system on a compact metric space is called universal (with respect to -limit sets) if, among its -limit sets, there is a homeomorphic copy of any -limit set of any dynamical system on . By a result of Pokluda and Smítal the unit interval admits a universal system. In this paper, we study the problem of the existence of universal systems on Cantor spaces, graphs, dendrites and higher-dimensional spaces. [Copyright &y& Elsevier]

Abstract: This paper studies proper -tuple edge-colorings of graphs that distinguish neighboring vertices by their sets of colors. Minimum numbers of colors for such colorings are determined for cycles, complete graphs and complete bipartite graphs. A variation in which the color sets assigned to edges have to form cyclic intervals is also studied and similar results are given. [Copyright &y& Elsevier]

Abstract: Let be a graph. A set is a restrained dominating set if every vertex in is adjacent to a vertex in and to a vertex in . The restrained domination number of , denoted , is the smallest cardinality of a restrained dominating set of . We will show that if is a connected graph of order and minimum degree and not isomorphic to one of nine exceptional graphs, then . [Copyright &y& Elsevier]

Abstract: Minimal triangulations and potential maximal cliques are the main ingredients for a number of polynomial time algorithms on different graph classes computing the treewidth of a graph. Potential maximal cliques are also the main engine of the fastest so far, exact (exponential) treewidth algorithm. Based on the recent results of Mazoit, we define the structures that can be regarded as minimal triangulations and potential maximal cliques for branchwidth: efficient triangulations and blocks. We show how blocks can be used to construct an algorithm computing the branchwidth of a graph on vertices in time . [Copyright &y& Elsevier]

Abstract: Let be a simple graph. For an edge of , the closed edge-neighbourhood of is the set . A function is called a signed edge domination function (SEDF) of if for every edge of . The signed edge domination number of is defined as . In this paper, we characterize all trees with signed edge domination numbers 1, 2, 3, or 4. [Copyright &y& Elsevier]

Abstract: For a graph , a subset of is called a shredder if consists of three or more components. We show that if is a 5-connected graph with , then the number of shredders of cardinality 5 of is less than or equal to . [Copyright &y& Elsevier]

Abstract: A set is a neighborhood set of G, if , where is the sub graph of G induced by v and all vertices adjacent to v. The neighborhood number of G is the minimum cardinality of a neighborhood set of G. In this paper, we extended the concept of neighborhood number and its relationship with other related parameters are explored. [Copyright &y& Elsevier]

Abstract: In this paper, we will show that the structure of the critical group of the graph is , where , where and are the two roots of the quadratic . [Copyright &y& Elsevier]