Search

A cactus is a connected graph in which any two cycles have at most one common vertex. In this article, we determine the unique graph with minimal distance spectral radius in the class of all cacti with n vertices and k cycles. Also, we determine the unique graph with minimal distance spectral radius in the class of all cacti with n vertices and r pendent vertices. Moreover, we determine the class of cacti in which the maximal distance spectral radius among all cacti with n vertices and k cycles is attained.

The eccentricity of a vertex is the maximum distance from it to another vertex and the average eccentricity $ecc (G)$ of a graph $G$ is the mean value of eccentricities of all vertices of $G$. The average eccentricity is deeply connected with a topological descriptor called the eccentric connectivity index, defined as a sum of products of vertex degrees and eccentricities. In this paper we analyze extremal properties of the average eccentricity, introducing two graph transformations that increase or decrease $ecc (G)$. Furthermore, we resolve four conjectures, obtained by the system AutoGraphiX, about the average eccentricity and other graph parameters (the clique number, the Randi\' c index and the independence number), refute one AutoGraphiX conjecture about the average eccentricity and the minimum vertex degree and correct one AutoGraphiX conjecture about the domination number., Comment: 15 pages, 3 figures

Let G be a connected graph with n>=2 vertices. Suppose that a fire breaks out at a vertex v of G. A firefighter starts to protect vertices. At each time interval, the firefighter protects two vertices not yet on fire. At the end of each time interval, the fire spreads to all the unprotected vertices that have a neighbour on fire. Let sn"2(v) denote the maximum number of vertices in G that the firefighter can save when a fire breaks out at vertex v. The surviving rate @r"2(G) of G is defined to be @?"v"@?"V"("G")sn"2(v)/n^2, which is the average proportion of saved vertices. In this paper, we show that if G is a planar graph with n>=2 vertices and without 4-cycles, then @r"2(G)>176.

The distance dG(u, v) between two vertices u and v in a connected graph G is the length of the shortest uv-path in G. A uv-path of length dG(u, v) is called a uv-geodesic. A set X is convex in G if vertices from all ab-geodesics belong to X for any two vertices a, b ∈ X. The convex domination number γcon(G) of a graph G equals the minimum cardinality of a convex dominating set. In the paper, Nordhaus-Gaddum-type results for the convex domination number are studied.

The eccentricity e (u) of a vertex u is the maximum distance of u to any other vertex in G. The distance degree sequence (dds) of a vertex v in a graph G = (V, E) is a list of the number of vertices at distance 1, 2, …, e (u) in that order, where e (u) denotes the eccentricity of u in G. Thus the sequence is the dds of the vertex vi in G where denotes number of vertices at distance j from Vi . A graph is distance degree regular (DDR) graph if all vertices have the same dds. A graph is distance degree injective (DDI) graph if no two vertices have same dds. In this paper we consider Cartesian and normal products of DDR and DDI graphs. Some structural results have been obtained along with some characterizations.

The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesn��k (1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesn��k by showing that for any two vertices v and w in a graph of diameter 2, if deg(v), 16 pages, 8 figures

Let T = (V, E) be a tree. A core of T is a path P, for which the sum of the weighted distances from all vertices to this path is minimized. In this paper, we consider the semi-obnoxious case in which the vertices have positive or negative weights. We prove that, when the sum of the weights of vertices is negative, the core must be a single vertex and that, when the sum of the vertices’ weights is zero there exists a core that is a vertex. Morgan and Slater (J Algorithms 1:247–258, 1980) presented a linear time algorithm to find the core of a tree with only positive weights of vertices. We show that their algorithm also works for semi-obnoxious problems.

We investigate the family of graphs with many large eigenvalues. It is not hard to see that every graph with many vertices of large degree that are pairwise at distance at least four from each other, has many large eigenvalues. We show that this does not hold if the vertices of large degree are at mutual distance three from each other. We explore this class of graphs further and provide some bounds on their eigenvalues.

Let G=(V,E) be a connected graph on n vertices. The proximity@p(G) of G is the minimum average distance from a vertex of G to all others. The eccentricitye(v) of a vertex v in G is the largest distance from v to another vertex, and the average eccentricity ecc(G) of the graph G is 1n@?"v"@?"V"("G")e(v). Recently, it was conjectured by Aouchiche and Hansen (2011) [3] that for any connected graph G on n>=3 vertices, ecc(G)-@p(G)=

An L(2,1,1)-labeling of a graph G assigns nonnegative integers to the vertices of G in such a way that labels of adjacent vertices differ by at least two, while vertices that are at distance at most three are assigned different labels. The maximum label used is called the span of the labeling, and the aim is to minimize this value. We show that the minimum span of an L(2,1,1)-labeling of a tree can be bounded by a lower and an upper bound with difference one. Moreover, we show that deciding whether the minimum span attains the lower bound is an NP-complete problem. This answers a known open problem, which was recently posed by King, Ras, and Zhou as well. We extend some of our results to general graphs and/or to more general distance constraints on the labeling.

International audience; Given a capacity, the set of dominating k-additive capacities is a convex polytope called the k-additive monotone core; thus, it is defined by its vertices. In this paper we deal with the problem of deriving a procedure to obtain such vertices in the line of the results of Shapley and Ichiishi for the additive case. We propose an algorithm to determine the vertices of the n-additive monotone core and we explore the possible translations for the k-additive case.

We consider the following on-line decision problem. The vertices of a realization of the random graph G(n,p) are being observed one by one by a selector. At time m, the selector examines the mth vertex and knows the graph induced by the m vertices that have already been examined. The selector’s aim is to choose the currently examined vertex maximizing the probability that this vertex has full degree, i.e. it is connected to all other vertices in the graph. An optimal algorithm for such a choice (in other words, optimal stopping time) is given. We show that it is of a threshold type and we find the threshold and its asymptotic estimation.

Let R and B be two sets of distinct points such that the points of R are coloured red and the points of B are coloured blue. Let G be a family of planar graphs such that for each graph in the family |R| vertices are red and |B| vertices are blue. The set R@?B is a universal point set for G if every graph G@?G has a straight-line planar drawing such that the blue vertices of G are mapped to the points of B and the red vertices of G are mapped to the points of R. In this paper we describe universal point sets for meaningful classes of 2-coloured trees and show applications of these results to the coloured simultaneous geometric embeddability problem.

LetΦ(G,λ)=det(λIn-L(G))=∑k=0n(-1)kck(G)λn-kbe the characteristic polynomial of the Laplacian matrix of a graphGof ordern. In this paper, we give four transforms on graphs that decrease all Laplacian coefficientsck(G)and investigate a conjecture A. Ilić and M. Ilić (2009) about the Laplacian coefficients of unicyclic graphs withnvertices andmpendent vertices. Finally, we determine the graph with the smallest Laplacian-like energy among all the unicyclic graphs withnvertices andmpendent vertices.

The betweenness centrality of a vertex of a graph is the portion of the shortest paths between all pairs of vertices passing through a given vertex. We study upper bounds for this invariant and its relations to the diameter and average distance of a graph.

Let G n r be the class of all connected graphs of order n with r pendent vertices. In this paper, we determine the unique graph with minimal distance spectral radius in G n r . In addition, we determine the unique graph with maximal distance spectral radius in G n r for each r ∈ { 2 , 3 , n - 3 , n - 2 , n - 1 } .

We deal with a very general problem: a given graph G is to be "packed" into a host graph H, and we are asked about some natural optimization questions concerning this packing. The problem has never been investigated before in this general form. The input of the problem is a simple graph G = (V, E) with lower and upper bounds on its edges and weights on its vertices. The vertices correspond to items which have to be packed into the vertices (bins) of a host graph, such that each host vertex can accommodate at most L weight in total, and if two items are adjacent in G, then the distance of their host vertices in H must be between the lower and upper bounds of the edge joining the two items. Special cases are bin packing with conflicts, chromatic number, and many more. We give some general structure statements, treat some special cases, and investigate the performance guarantee of polynomial-time algorithms both in the offline and online setting.

Many shape descriptors based on the boundary have been developed for feature extraction and pattern matching/recognition of objects. This paper presents a novel algorithm to segment a traced boundary in open and closed sub-sections. The obtained sub-sections can be utilized for generating more features while being one of the features. A traced boundary has been considered as an undirected graph with pixels representing the vertices. It is proved that ''For a boundary traced using 8-connectivity maximum degree of a vertex cannot exceed four''. This aspect and the instances of degree and number of occurrences are used to categorize all the vertices in eight exhaustive types. Six of these are identified as critical vertices. The segmentation is done based on the principle that in an Eulerian circuit, each edge is traversed only once. Further segregation in open and closed sub-graphs is done by choosing critical vertices at a minimum directed distance. The testing of the algorithm has been done on artificially generated images and from different databases of hand written text. The performance analysis shows that the execution time is a linear function of the number of occurrences of each type of the vertices. The performance analysis is further supported using multiple regression.

Let D ( G ) = ( d i , j ) n i? n denote the distance matrix of a connected graph G with order n , where d i j is equal to the distance between v i and v j in G . The largest eigenvalue of D ( G ) is called the distance spectral radius of graph G , denoted by ? ( G ) . In this paper, we give some graft transformations that decrease and increase ? ( G ) and prove that the graph S n ' (obtained from the star S n on n ( n is not equal to 4, 5) vertices by adding an edge connecting two pendent vertices) has minimal distance spectral radius among unicyclic graphs on n vertices; while P n ' (obtained from a triangle K 3 by attaching pendent path P n - 3 to one of its vertices) has maximal distance spectral radius among unicyclic graphs on n vertices. Highlights? Some new graft transformations that increase distance spectral radius are presented. ? Graphs with minimal distance spectral radius among unicyclic graphs are determined. ? Graphs with maximal distance spectral radius among unicyclic graphs are determined.

Given a 3-vertex-connected triangular planar graph and an embedding of its boundary vertices, can the interior vertices be embedded to form a valid triangulation? We describe an algorithm which decides this problem and produces such an embedding if it exists.

Let [Formula: see text] be the set of unicyclic graphs with n vertices and k cut vertices. In this paper, we determine the unique graph with the maximal spectral radius among all graphs in [Formula: see text] for 1 ≤ k ≤ n - 3.

A set of vertices S in a graph is convex if it contains all vertices which belong to shortest paths between vertices in S. The convexity number c(G) of a graph G is the maximum cardinality of a convex set of vertices which does not contain all vertices of G. We prove NP-completeness of the problem to decide for a given bipartite graph G and an integer k whether c(G) ≥ k. Furthermore, we identify natural necessary extension properties of graphs of small convexity number and study the interplay between these properties and upper bounds on the convexity number.

Let G be a graph of order n and 3≤t≤n/4 be an integer. Recently, Kaneko and Yoshimoto [J Combin Theory Ser B 81(1) (2001), 100–109] provided a sharp δ(G) condition such that for any set X of t vertices, G contains a hamiltonian cycle H so that the distance along H between any two vertices of X is at least n/2t. In this article, minimum degree and connectivity conditions are determined such that for any graph G of sufficiently large order n and for any set of t vertices X⊆V(G), there is a hamiltonian cycle H so that the distance along H between any two consecutive vertices of X is approximately n/t. Furthermore, the minimum degree threshold is determined for the existence of a hamiltonian cycle H such that the vertices of X appear in a prescribed order at approximately predetermined distances along H. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 28–45, 2012

In this paper, we give some results on Laplacian spectral radius of graphs with cut vertices, and as their applications, we also determine the unique graph with the largest Laplacian spectral radius among all unicyclic graphs with n vertices and diameter d, 3⩽d⩽n−3.

Let G be a connected graph and d(x,y) be the distance between the vertices x and y. A subset of vertices W={w"1,w"2,...,w"k} is called a resolving set for G if for every two distinct vertices x,y@?V(G), there is a vertex w"i@?W such that d(x,w"i) d(y,w"i). A resolving set containing a minimum number of vertices is called a metric basis for G and the number of vertices in a metric basis is its metric dimension dim(G). A family G of connected graphs is a family with constant metric dimension if dim(G) is finite and does not depend upon the choice of G in G. In this paper, we study the metric dimension of some classes of convex polytopes which are obtained by the combinations of two different graph of convex polytopes. It is shown that these classes of convex polytopes have the constant metric dimension and only three vertices chosen appropriately suffice to resolve all the vertices of these classes of convex polytopes.

In this paper, we show that among all the connected graphs with n vertices and k cut vertices, the maximal signless Laplacian spectral radius is attained uniquely at the graph Gn,k, where Gn,k is obtained from the complete graph Kn-k by attaching paths of almost equal lengths to all vertices of Kn-k. We also give a new proof of the analogous result for the spectral radius of the connected graphs with n vertices and k cut vertices (see [A. Berman, X.-D. Zhang, On the spectral radius of graphs with cut vertices, J. Combin. Theory Ser. B 83 (2001) 233–240]). Finally, we discuss the limit point of the maximal signless Laplacian spectral radius.

In this paper, the effects on the signless Laplacian spectral radius of a graph are studied when some operations, such as edge moving, edge subdividing, are applied to the graph. Moreover, the largest signless Laplacian spectral radius among the all unicyclic graphs with n vertices and k pendant vertices is identified. Furthermore, we determine the graphs with the largest Laplacian spectral radii among the all unicyclic graphs and bicyclic graphs with n vertices and k pendant vertices, respectively.

The distance spectral radius @r(G) of a graph G is the largest eigenvalue of the distance matrix D(G). Recently, many researches proposed the use of @r(G) as a molecular structure descriptor of alkanes. In this paper, we introduce general transformations that decrease distance spectral radius and characterize n-vertex trees with given matching number m which minimize the distance spectral radius. The extremal tree A(n,m) is a spur, obtained from the star graph S"n"-"m"+"1 with n-m+1 vertices by attaching a pendent edge to each of certain m-1 non-central vertices of S"n"-"m"+"1. The resulting trees also minimize the spectral radius of adjacency matrix, Hosoya index, Wiener index and graph energy in the same class of trees. In conclusion, we pose a conjecture for the maximal case based on the computer search among trees on n@?24 vertices. In addition, we found the extremal tree that uniquely maximizes the distance spectral radius among n-vertex trees with perfect matching and fixed maximum degree @D.

In this paper, we determine graphs with the largest Laplacian spectral radius among the unicyclic and the bicyclic graphs on n vertices with k pendant vertices, respectively.

There are only few results concerning crossing numbers of join of some graphs. In the paper, for the special graph H on six vertices we give the crossing numbers of its join with n isolated vertices as well as with the path Pn on n vertices and with the cycle Cn.

The spectral excess theorem provides a quasi-spectral characterization for a (regular) graph Γ with d+1 distinct eigenvalues to be distance-regular graph, in terms of the excess (number of vertices at distance d) of each of its vertices. The original approach, due to Fiol and Garriga in 1997, was obtained by using a local approach, so giving a characterization of the so-called pseudo-distance-regularity around a vertex. In this paper we present a new simple projection method based in a global point of view, and where the mean excess plays an essential role.

Betweenness-Centrality measure is often used in social and computer communication networks to estimate the potential monitoring and control capabilities a vertex may have on data flowing in the network. In this article, we define the Routing Betweenness Centrality (RBC) measure that generalizes previously well known Betweenness measures such as the Shortest Path Betweenness, Flow Betweenness, and Traffic Load Centrality by considering network flows created by arbitrary loop-free routing strategies. We present algorithms for computing RBC of all the individual vertices in the network and algorithms for computing the RBC of a given group of vertices, where the RBC of a group of vertices represents their potential to collaboratively monitor and control data flows in the network. Two types of collaborations are considered: (i) conjunctive—the group is a sequences of vertices controlling traffic where all members of the sequence process the traffic in the order defined by the sequence and (ii) disjunctive—the group is a set of vertices controlling traffic where at least one member of the set processes the traffic. The algorithms presented in this paper also take into consideration different sampling rates of network monitors, accommodate arbitrary communication patterns between the vertices (traffic matrices), and can be applied to groups consisting of vertices and/or edges. For the cases of routing strategies that depend on both the source and the target of the message, we present algorithms with time complexity of O ( n 2 m ) where n is the number of vertices in the network and m is the number of edges in the routing tree (or the routing directed acyclic graph (DAG) for the cases of multi-path routing strategies). The time complexity can be reduced by an order of n if we assume that the routing decisions depend solely on the target of the messages. Finally, we show that a preprocessing of O ( n 2 m ) time, supports computations of RBC of sequences in O ( kn ) time and computations of RBC of sets in O ( n 3 n ) time, where k in the number of vertices in the sequence or the set.

A graph G is a cactus if any two of its cycles have at most one common vertex. In this article, we determine graphs with the largest spectral radius among all the cacti with n vertices and k-pendant vertices.

A set of vertices $C$ in a graph is convex if it contains all vertices which lie on shortest paths between vertices in $C$. The convex hull of a set of vertices $S$ is the smallest convex set containing $S$. The hull number $h(G)$ of a graph $G$ is the smallest cardinality of a set of vertices whose convex hull is the vertex set of $G$. For a connected triangle-free graph $G$ of order $n$ and diameter $d$ at least 4, we prove that $h(G)\leq(n-d+3)/3$ if $G$ has minimum degree at least 3 and that $h(G)\leq2(n-d+5)/7$, if $G$ is cubic. Furthermore for a connected graph $G$ of order $n$, girth $g$ at least 5, minimum degree at least 2, and diameter $d$, we prove $h(G)\leq2+(n-d-1)/\left\lceil\frac{g-1}{2}\right\rceil$. All bounds are best possible.

In this paper, we analyze parameter improvement under vertex fusion in a graph G. This is a setting in which a new graph G′ is obtained after identifying a subset of vertices of G in a single vertex. We are interested in distance parameters, in particular diameter, radius and eccentricity of a vertex v. We show that the corresponding problem is NP-Complete for the three parameters. We also find graph classes in which the problem can be solved in polynomial time.

In this paper, we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set S of vertices whose induced subgraph has a perfect matching. The set S is called a differentiating-paired dominating set if for every pair of distinct vertices u and v in V(G), N[u]∩S≠N[v]∩S, where N[u] denotes the set consisting of u and all vertices adjacent to u. In this paper, we provide a constructive characterization of trees that do not have a differentiating-paired dominating set.

The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. In this paper, we define two vertices as maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. Moreover, we show that an (n-1)-regular Cayley graph generated by transposition tree is maximally local-connected, even if there are at most (n-3) faulty vertices in it, and prove that it is also (n-1)-fault-tolerant one-to-many maximally local-connected.

Let G be a graph in which each vertex can be in one of two states: on or off. In the σ-game, when you “push” a vertex v you change the state of all of its neighbors, while in the σ+-game you change the state of v as well. Given a starting configuration of on vertices, the object of both games is to reduce it, by a sequence of pushes, to the smallest possible number of on vertices. We show that any starting configuration in a graph with no isolated vertices can, by a sequence of pushes, be reduced to at most half on, and we characterize those graphs for which you cannot do better. The proofs use techniques from coding theory. In the lit-only versions of these two games, you can only push vertices which are on. We obtain some results on the minimum number of on vertices one can obtain in grid graphs in the regular and lit-only versions of both games.

Let U ( n , k ) be the set of unicyclic graphs with n vertices and k pendant vertices. In this paper, we determine the unique graph with the minimal least eigenvalue among all graphs in U ( n , k ) . The work is related with that of Guo [S.G. Guo, The spectral radius of unicyclic and bicyclic graphs with n vertices and k pendant vertices, Linear Algebra Appl. 408 (2005) 78–85], which determined the unicyclic graph with the maximal spectral radius in U ( n , k ) . We can observe that the extremal graph on the least eigenvalue is different from that on the spectral radius.

A graph is walk-regular if the number of cycles of length rooted at a given vertex is a constant through all the vertices. For a walk-regular graph G with d+1 different eigenvalues and spectrally maximum diameter D = d, we study the geometry of its d-cliques, that is, the sets of vertices which are mutually at distance d. When these vertices are projected onto an eigenspace of its adjacency matrix, we show that they form a regular tetrahedron and we compute its parameters. Moreover, the results are generalized to the case of k-walk-regular graphs, a family which includes both walk-regular and distance-regular graphs, and their t-cliques or vertices at distance t from each other.

Tricyclic graphs are connected graphs in which the number of edges equals the number of vertices plus two. In this paper, we determine the graph with the largest Laplacian spectral radius among all tricyclic graphs with n vertices and k pendant vertices.

Motivated by DNA rearrangements and DNA homologous recombination modeled in [A. Angeleska, N. Jonoska, M. Saito, L.F. Landweber, RNA-guided DNA assembly, Journal of Theoretical Biology, 248(4) (2007), 706-720], we investigate smoothings on graphs that consist of only 4-valent and 1-valent rigid vertices, called assembly graphs. An assembly graph can be seen as a representation of the DNA during certain recombination processes in which 4-valent vertices correspond to the alignment of the recombination sites. A single gene is modeled by a polygonal path in an assembly graph. A polygonal path makes a ''right-angle'' turn at every vertex, defining smoothings at the 4-valent vertices and therefore modeling the recombination process. We investigate the minimal number of polygonal paths visiting all vertices of a given graph exactly once, and show that for every positive integer n there are graphs that require at least n such polygonal paths. We show that there is an embedding in three-dimensional space of each assembly graph such that smoothing of vertices according to a given set of polygonal paths results in an unlinked graph. As some recombination processes may happen simultaneously, we characterize the subsets of vertices whose simultaneous smoothings keep a given gene in tact and give a characterization of all sequences of sets of vertices defining successive simultaneous smoothings that can realize complete gene rearrangement.

Let G be a connected graph and let S be a set of vertices in G. The Steiner distance d(S) of S is the minimum size of a subtree of G containing S. Such a subtree of size d(S) is a Steiner tree for S. The set S is g-convex if it contains the set of all vertices that lie on some shortest u–v path in G for every pair u and v of vertices in S. The set S is k-Steiner convex, denoted by gk-convex, if for every k-element subset R of S, every vertex that belongs to some Steiner tree for R is also in S. Thus, S is g2-convex if and only if it is g-convex. In this paper, we distinguish three local convexity notions for g3-convexity and we characterize the graphs for which two of these conditions hold. For the third condition we determine some necessary conditions and some sufficient conditions for the graph class satisfying this condition.

We consider the problem of simplifying a planar triangle mesh using edge contractions, under the restriction that the resulting vertices must be a subset of the input set. That is, contraction of an edge must be made onto one of its adjacent vertices, which results in removing the other adjacent vertex. We show that if the perimeter of the mesh consists of at most five vertices, then we can always find a vertex not on the perimeter which can be removed in this way. If the perimeter consists of more than five vertices such a vertex may not exist. In order to maintain a higher number of removable vertices under the above restriction, we study edge flips which can be performed in a visually smooth way. A removal of a vertex which is preceded by one such smooth operation is called a 2-step removal. Moreover, we introduce the possibility that the user defines "important" vertices (or edges) which have to remain intact. Given m such important vertices, or edges, we show that a simplification hierarchy of size O(n) and depth O( log (n/m)) can be constructed by 2-step removals in O(n) time, such that the simplified graph contains the m important vertices and edges, and at most O(m) other vertices from the input graph. In some triangulations, many vertices may not even be 2-step removable. In order to provide the option to remove such vertices, we also define and examine k-step removals. This increases the lower bound on the number of removable vertices.

This paper studies the problem of broadcasting in synchronous point-to-point networks, where one initiator owns a piece of information that has to be transmitted to all other vertices as fast as possible. The model of fractional dynamic faults with threshold is considered: in every step either a fixed number $T$, or a fraction $\alpha$, of sent messages can be lost depending on which quantity is larger. As the main result we show that in complete graphs and hypercubes it is possible to inform all but a constant number of vertices, exhibiting only a logarithmic slowdown, i.e. in time $O(D\log n)$ where $D$ is the diameter of the network and $n$ is the number of vertices. Moreover, for complete graphs under some additional conditions (sense of direction, or $\alpha, Comment: Conference: Sirocco 2007

A circuit graph(G,C) is a 2-connected plane graph G with an outer cycle C such that from each inner vertex v, there are three disjoint paths to C. In this paper, we shall show that a circuit graph with n vertices has a 3-tree (i.e., a spanning tree with maximum degree at most 3) with at most n-73 vertices of degree 3. Our estimation for the number of vertices of degree 3 is sharp. Using this result, we prove that a 3-connected graph with n vertices on a surface F"@g with Euler characteristic @g>=0 has a 3-tree with at most n3+c"@g vertices of degree 3, where c"@g is a constant depending only on F"@g.

In the NP-hard Cluster Editing problem, we have as input an undirected graph G and an integer k>=0. The question is whether we can transform G, by inserting and deleting at most k edges, into a cluster graph, that is, a union of disjoint cliques. We first confirm a conjecture by Michael Fellows [IWPEC 2006] that there is a polynomial-time kernelization for Cluster Editing that leads to a problem kernel with at most 6k vertices. More precisely, we present a cubic-time algorithm that, given a graph G and an integer k>=0, finds a graph G^' and an integer k^'@?k such that G can be transformed into a cluster graph by at most k edge modifications iff G^' can be transformed into a cluster graph by at most k^' edge modifications, and the problem kernel G^' has at most 6k vertices. So far, only a problem kernel of 24k vertices was known. Second, we show that this bound for the number of vertices of G^' can be further improved to 4k vertices. Finally, we consider the variant of Cluster Editing where the number of cliques that the cluster graph can contain is stipulated to be a constant d>0. We present a simple kernelization for this variant leaving a problem kernel of at most (d+2)k+d vertices.

A graph G on n vertices is called a Dirac graph if it has a minimum degree of at least n/2. The distance dist"G(u,v) is defined as the number of edges in a shortest path of G joining u and v. In this paper we show that in a Dirac graph G, for every small enough subset S of the vertices, we can distribute the vertices of S along a Hamiltonian cycle C of G in such a way that all but two pairs of subsequent vertices of S have prescribed distances (apart from a difference of at most 1) along C. More precisely we show the following. There are @w,n"0>0 such that if G is a Dirac graph on n>=n"0 vertices, d is an arbitrary integer with [email protected][email protected][email protected]/2 and S is an arbitrary subset of the vertices of G with [email protected]?|S|[email protected][email protected]/d, then for every sequence d"i of integers with [email protected]?d"[email protected]?d,[email protected][email protected]?k-1, there is a Hamiltonian cycle C of G and an ordering of the vertices of S, a"1,a"2,...,a"k, such that the vertices of S are visited in this order on C and we have |dist"C(a"i,a"i"+"1)-d"i|@?1,for all but [email protected][email protected]?k-1.

In order to make a full evaluation of an interconnection network, it is essential to estimate the minimum size of a largest connected component of this network provided the faulty vertices in the network may break its connectedness. Star graphs are recognized as promising candidates for interconnection networks. This article addresses the size of a largest connected component of a faulty star graph. We prove that, in an n-star graph (n≥3) with up to 2n-4 faulty vertices, all fault-free vertices but at most two form a connected component. Moreover, all fault-free vertices but exactly two form a connected component if and only if the set of all faulty vertices is equal to the neighbourhood of a pair of fault-free adjacent vertices. These results show that star graphs exhibit excellent fault-tolerant abilities in the sense that there exists a large functional network in a faulty star graph.

We study sets of points in the two-dimensional Euclidean plane. The relative neighbourhood graph (RNG) of a point set is a straight line graph that connects two points from the point set if and only if there is no other point in the set that is closer to both points than they are to each other. A triangulation of a point set is a maximal set of nonintersecting line segments (called edges) with vertices in the point set. We introduce angular restrictions in the triangulations. Using the well-known method of exclusion regions, we show that the relative neighbourhood graph is a part of every triangulation all of the angles of which are greater than or equal to 30^o.