Search

We are concerned with families of graphs in which there is a single root-vertex ofunbounded valence, and in which, however, there is a uniform upper bound for the valences of all the other vertices. Using a result of Zagier, we obtain formulas and recursions for the genus distributions of several such families, including the wheel graphs. We show that the region distribution of a wheel graph is approximately proportional to the sequence of Stirling numbers of the first kind. Stahl has previously obtained such a result for embeddings in surfaces whose genus is relatively near to the maximum genus. Here, we generalize Stahl’s result to the entire genus distributions of wheels. Moreover, we derive the genus distributions for four other graph families that have some similarities to wheels.

The vertices of Kneser graph K ( n , k ) are the subsets of { 1 , 2 , … , n } of cardinality k , two vertices are adjacent if and only if they are disjoint. The square G 2 of a graph G is defined on the vertex set of G with two vertices adjacent if their distance in G is at most 2. Z. Furedi, in 2002, proposed the problem of determining the chromatic number of the square of the Kneser graph. The first non-trivial problem arises when n = 2 k + 1 . It is believed that χ ( K 2 ( 2 k + 1 , k ) ) = 2 k + c where c is a constant, and yet the problem remains open. The best known upper bounds are by Kim and Park: 8 k ∕ 3 + 20 ∕ 3 for 1 k ≥ 3 (Kim and Park, 2014) and 32 k ∕ 15 + 32 for k ≥ 7 (Kim and Park, 2016). In this paper, we develop a new approach to this coloring problem by employing graph homomorphisms, cartesian products of graphs, and linear congruences integrated with combinatorial arguments. These lead to χ ( K 2 ( 2 k + 1 , k ) ) ≤ 5 k ∕ 2 + c , where c is a constant in { 5 ∕ 2 , 9 ∕ 2 , 5 , 6 } , depending on k ≥ 2 .

Given two simple graphs G and H, the Ramsey number R ( G , H ) is the smallest integer n such that for any graph of order n, either it contains G or its complement contains H. Let T n be a tree graph of order n and W s , m be the generalised wheel graph K s + C m . In this paper, we show that for n ≥ 5 , s ≥ 2 , R ( T n , W s , 6 ) = ( s + 1 ) ( n − 1 ) + 1 and for n ≥ 5 , s ≥ 1 , R ( T n , W s , 7 ) = ( s + 2 ) ( n − 1 ) + 1 . We also determine the exact value of R ( T n , W s , m ) for large n and s.

A class of graphs is $\chi$-bounded if there exists a function $f:\mathbb N\rightarrow \mathbb N$ such that for every graph $G$ in the class and an induced subgraph $H$ of $G$, if $H$ has no clique of size $q+1$, then the chromatic number of $H$ is less than or equal to $f(q)$. We denote by $W_n$ the wheel graph on $n+1$ vertices. We show that the class of graphs having no vertex-minor isomorphic to $W_n$ is $\chi$-bounded. This generalizes several previous results; $\chi$-boundedness for circle graphs, for graphs having no $W_5$ vertex-minors, and for graphs having no fan vertex-minors., Comment: 27 pages, 9 figures (revised version)

Let G be an edge-colored graph. The minimum color degree of G is the minimum number of different colors appearing on the edges incident with the vertices of G. In this paper, we study the existence of properly edge-colored cycles in (not necessarily properly) edge-colored complete graphs. Fujita and Magnant (2011) conjectured that in an edge-colored complete graph on n vertices with minimum color degree at least (n+1)∕2, each vertex is contained in a properly edge-colored cycle of length k, for all k with 3≤k≤n. They confirmed the conjecture for k=3 and k=4, and they showed that each vertex is contained in a properly edge-colored cycle of length at least 5 when n≥13, but even the existence of properly edge-colored Hamilton cycles is unknown (in complete graphs that satisfy the conditions of the conjecture). We prove a cycle extension result that implies that each vertex is contained in a properly edge-colored cycle of length at least the minimum color degree.

For a connected simple graph embedded into a 2-sphere, we show that the number of vertices of the graph is less than or equal to 380 if the degree of each vertex is at least three, the combinatorial vertex curvature is positive everywhere, and the graph is different from prisms and antiprisms. This gives a new upper bound for the constant brought up by DeVos and Mohar in their paper from 2007. We also show that if a graph is embedded into a projective plane instead of a 2-sphere but satisfies the other properties listed above, then the number of vertices is at most 190.

The packing chromatic number $\chi_{\rho}(G)$ of a graph $G$ is the smallest integer $k$ such that there exists a $k$-vertex coloring of $G$ in which any two vertices receiving color $i$ are at distance at least $i+1$. It is proved that in the class of subcubic graphs the packing chromatic number is bigger than $13$, thus answering an open problem from [Gastineau, Togni, $S$-packing colorings of cubic graphs, Discrete Math.\ 339 (2016) 2461--2470]. In addition, the packing chromatic number is investigated with respect to several local operations. In particular, if $S_e(G)$ is the graph obtained from a graph $G$ by subdividing its edge $e$, then $\left\lfloor \chi_{\rho}(G)/2 \right\rfloor +1 \le \chi_{\rho}(S_e(G)) \le \chi_{\rho}(G)+1$., Comment: 11 pages, 4 figures

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

Let G be a graph, and let S be a subset of the vertex set of G . We denote the set of the end vertices of a path P by e n d ( P ) . A path P is an S -path if | V ( P ) | ≥ 2 and V ( P ) ∩ S = e n d ( P ) . An S -path-system is a graph H such that H contains all vertices of S and every component of H is an S -path. In this paper, we give a sharp degree sum condition for a bipartite graph to have a spanning S -path-system.

Besirik, Ayse/0000-0002-3980-196X, WOS: 000517221700007, The stability of a communication network has a great importance in network design. There are several vulnerability measures used to determine the resistance of network to the disruption in this sense. Domination theory provides a model to measure the vulnerability of a graph network. A new vulnerability measure of domination integrity was introduced by Sundareswaran in his Ph.D. thesis (Parameters of vulnerability in graphs (2010)) and defined as DI(G) = min{|S| + m(G - S):S is an element of V(G)} where m(G - S) denotes the order of a largest component of graph G - S and S is a dominating set of G. the domination integrity of an undirected connected graph is such a measure that works on the whole graph and also the remaining components of graph after any break down. Here we determine the domination integrity of wheel graph W-1,W-n, Ladder graph L-n, S-m,S-n, Friendship graph F-n, Thorn graph of P-n and C-n which are commonly used graph models in network design.

A wheel graph is a graph formed by connecting a single vertex to all vertices of a cycle. A graph is called wheel-free if it does not contain any wheel graph as a subgraph. In 2010, Nikiforov proposed a Brualdi-Solheid-Tur\'{a}n type problem: what is the maximum spectral radius of a graph of order $n$ that does not contain subgraphs of particular kind. In this paper, we study the Brualdi-Solheid-Tur\'{a}n type problem for wheel-free graphs, and we determine the maximum (signless Laplacian) spectral radius of a wheel-free graph of order $n$. Furthermore, we characterize the extremal graphs., Comment: 20 pages, 3 figures

It is well-known (as a special case of the path-path Ramsey number) that in every 2-coloring of the edges of K 3 n - 1 , the complete graph on 3 n - 1 vertices, there is a monochromatic P 2 n , a path on 2 n vertices. Schelp conjectured that this statement remains true if K 3 n - 1 is replaced by any host graph on 3 n - 1 vertices with minimum degree at least 3 ( 3 n - 1 ) 4 . Here we propose the following stronger conjecture, allowing host graphs with the corresponding Ore-type condition: If G is a graph on 3 n - 1 vertices such that for any two non-adjacent vertices u and v , d G ( u ) + d G ( v ) ? 3 2 ( 3 n - 1 ) , then in any 2-coloring of the edges of G there is a monochromatic path on 2 n vertices. Our main result proves the conjecture in a weaker form, replacing P 2 n by a connected matching of size n . Here a monochromatic, say red, matching in a 2-coloring of the edges of a graph is connected if its edges are all in the same connected component of the graph defined by the red edges. Applying the standard technique of converting connected matchings to paths with the Regularity Lemma, we use this result to get an asymptotic version of our conjecture for paths.

We show that, every oriented graph with maximum average degree less than 28/9 admits a homomorphism into the Paley tournament with 11 vertices.

We generalize the following two seminal results.(1)Thomassen's result 15] in 1983, which says that every 4-connected planar graph is Hamiltonian-connected (which generalizes the old result of Tutte 16] in 1956, which says that every 4-connected planar graph is Hamiltonian).(2)Thomas and Yu's result 12] in 1994, which says that every 4-connected projective-planar graph is Hamiltonian. Here, Hamiltonian-connected means that for any two vertices u , v , there is a Hamiltonian path between u and v (and hence this generalizes the existence of Hamiltonian cycles).Specifically, we prove the following; Every 4-connected projective-planar graph is Hamiltonian-connected.This proves a conjecture of Dean 3] in 1990. Our result is best possible in many senses. First, we cannot lower the connectivity 4. Secondly, we cannot generalize our result to a surface with higher genus (that is, there is a 4-connected graph on the torus or on the Klein bottle which is not Hamiltonian-connected).Our proof is constructive in a sense that there is a polynomial time algorithm to find, given two vertices in a 4-connected projective-planar graph, a Hamiltonian path between these two vertices.

Let T be an edge-weighted tree and let d min , d max be two nonnegative real numbers. The pairwise compatibility graph (PCG) of T is a graph G such that each vertex of G corresponds to a distinct leaf of T and two vertices are adjacent in G if and only if the weighted distance between their corresponding leaves in T is in the interval d min , d max . Similarly, a given graph G is a PCG if there exist suitable T , d min , d max , such that G is a PCG of T. Yanhaona, Bayzid and Rahman proved that there exists a graph with 15 vertices that is not a PCG. On the other hand, Calamoneri, Frascaria and Sinaimeri proved that every graph with at most seven vertices is a PCG. In this paper we construct a graph of eight vertices that is not a PCG, which strengthens the result of Yanhaona, Bayzid and Rahman, and implies optimality of the result of Calamoneri, Frascaria and Sinaimeri. We then construct a planar graph with sixteen vertices that is not a PCG. Finally, we prove a variant of the PCG recognition problem to be NP-complete.

The Bose-Hubbard model is a system of interacting bosons that live on the vertices of a graph. The particles can move between adjacent vertices and experience a repulsive on-site interaction. The Hamiltonian is determined by a choice of graph that specifies the geometry in which the particles move and interact. We prove that approximating the ground energy of the Bose-Hubbard model on a graph at fixed particle number is QMA-complete. In our QMA-hardness proof, we encode the history of an n-qubit computation in the subspace with at most one particle per site (i.e., hard-core bosons). This feature, along with the well-known mapping between hard-core bosons and spin systems, lets us prove a related result for a class of 2-local Hamiltonians defined by graphs that generalizes the XY model. By avoiding the use of perturbation theory in our analysis, we circumvent the need to multiply terms in the Hamiltonian by large coefficients.

The \emph{Tur��n function} $\ex(n,F)$ of a graph $F$ is the maximum number of edges in an $F$-free graph with $n$ vertices. The classical results of Tur��n and Rademacher from 1941 led to the study of supersaturated graphs where the key question is to determine $h_F(n,q)$, the minimum number of copies of $F$ that a graph with $n$ vertices and $\ex(n,F)+q$ edges can have. We determine $h_F(n,q)$ asymptotically when $F$ is \emph{color-critical} (that is, $F$ contains an edge whose deletion reduces its chromatic number) and $q=o(n^2)$. Determining the exact value of $h_F(n,q)$ seems rather difficult. For example, let $c_1$ be the limit superior of $q/n$ for which the extremal structures are obtained by adding some $q$ edges to a maximum $F$-free graph. The problem of determining $c_1$ for cliques was a well-known question of Erd\H os that was solved only decades later by Lov��sz and Simonovits. Here we prove that $c_1>0$ for every {color-critical}~$F$. Our approach also allows us to determine $c_1$ for a number of graphs, including odd cycles, cliques with one edge removed, and complete bipartite graphs plus an edge., 27 pages, 2 figures

Let G be a 3-partite graph with k vertices in each part and suppose that between any two parts, there is no cycle of length four. Fischer and Matousek asked for the maximum number of triangles in such a graph. A simple construction involving arbitrary projective planes shows that there is such a graph with ( 1 − o ( 1 ) ) k 3 / 2 triangles, and a double counting argument shows that one cannot have more than ( 1 + o ( 1 ) ) k 7 / 4 triangles. Using affine planes defined by specific planar polynomials over finite fields, we improve the lower bound to ( 1 − o ( 1 ) ) k 5 / 3 .

We describe a polynomial time algorithm to decide for a given connected graph G and a given partition of its vertex set into two sets A and B, whether it is possible to assign a closed interval I(u) to each vertex u of G such that two distinct vertices u and v of G are adjacent if and only if I(u) and I(v) intersect, all intervals assigned to vertices in A have some length L"A, and all intervals assigned to vertices in B have some length L"B where L"A

The lower bound for the chromatic number of $$\mathbb {R}^4$$R4 is improved from $$7$$7 to $$9$$9. Three graphs with unit distance embeddings in $$\mathbb {R}^4$$R4 are described. The first is a $$7$$7-chromatic graph of order $$14$$14 whose chromatic number can be verified by inspection. The second is an $$8$$8-chromatic graph of order $$26$$26. In this case the chromatic number can be verified quickly by a simple computer program. The third graph is a $$9$$9-chromatic graph of order $$65$$65 for which computer verification takes about one minute.

A chromatic root is a root of the chromatic polynomial of a graph. While the real chromatic roots have been extensively studied and well understood, little is known about the real parts of chromatic roots. It is not difficult to see that the largest real chromatic root of a graph with n vertices is n − 1 , and indeed, it is known that the largest real chromatic root of a graph is at most the tree-width of the graph. Analogous to these facts, it was conjectured in Dong et al. (2005) that the real parts of chromatic roots are also bounded above by both n − 1 and the tree-width of the graph. In this article we show that for all k ≥ 2 there exist infinitely many graphs G with tree-width k such that G has non-real chromatic roots z with ℜ ( z ) > k . We also discuss the weaker conjecture and prove it for graphs G with χ ( G ) ≥ n − 3 .

In this paper necessary and sufficient conditions are found for the existence of a $$4$$4-cycle system of a complete graph on $$n$$n vertices with leave a nearly $$2$$2-regular graph (that is, a not necessarily spanning graph in which all vertices have degree 2 except for one of degree greater than 2).

For a graph G, we denote by ?(G) the minimum degree of G. A graph G is said to be claw-free if G has no induced subgraph isomorphic to K 1, 3. In this article, we prove that every claw-free graph G with minimum degree at least 4 has a 2-factor in which each cycle contains at least $${\big\lceil\frac{\delta(G) - 1}{2}\big\rceil}$$ ? ? ( G ) - 1 2 ? vertices and every 2-connected claw-free graph G with minimum degree at least 3 has a 2-factor in which each cycle contains at least ?(G) vertices. For the case where G is 2-connected, the lower bound on the length of a cycle is best possible.

An acyclic k-coloring of a graph G is a mapping @f from the set of vertices of G to a set of k distinct colors such that no two adjacent vertices receive the same color and @f does not contain any bichromatic cycle. In this paper we prove that every planar graph with n vertices has a 1-subdivision that is acyclically 3-colorable (respectively, 4-colorable), where the number of division vertices is at most 2n-5 (respectively, n-3). On the other hand, we prove a 1.28n (respectively, 0.3n) lower bound on the number of division vertices for acyclic 3-colorings (respectively, 4-colorings) of planar graphs. Furthermore, we establish the NP-completeness of deciding acyclic 4-colorability for graphs with maximum degree 5 and for planar graphs with maximum degree 7.

We define a family of pseudo-telepathy games using graph states that extends the Mermin games. This family also contains a game used to define a quantum probability distribution that cannot be simulated by any number of nonlocal boxes. We extend this result, proving that the probability distribution obtained by the Paley graph state on 13 vertices (each vertex corresponds to a player) cannot be simulated by any number of 4-partite nonlocal boxes and that the Paley graph states on $k^{2}2^{2k-2}$ vertices provide a probability distribution that cannot be simulated by $k$-partite nonlocal boxes, for any $k$.

When G is a graph with average degree greater than k − 2 , Erdős and Gallai proved that G contains a path on k vertices. Erdős and Sos conjectured that under the same condition, G should contain every tree on k vertices. Several results based upon the number of vertices in G have been proved including the special cases where G has exactly k vertices (Zhou), k + 1 vertices (Slater, Teo and Yap), k + 2 vertices (Woźniak) and k + 3 vertices (Tiner). To strengthen these results, we will prove that the Erdős-Sos conjecture holds when the graph G contains no path with k + 4 vertices (no restriction is imposed on the number of vertices of G ).

Given a fixed positive integer k ≥ 2, let G be a simple graph of order n ≥ 6k. It is proved that if the minimum degree of G is at least n/2 + 1, then for every pair of vertices x and y, there exists a Hamiltonian cycle such that the distance between x and y along that cycle is precisely k.

Let k be a non-negative integer. A branch vertex of a tree is a vertex of degree at least three. We show two sufficient conditions for a connected claw-free graph to have a spanning tree with a bounded number of branch vertices: (i) A connected claw-free graph has a spanning tree with at most k branch vertices if its independence number is at most 2k + 2. (ii) A connected claw-free graph of order n has a spanning tree with at most one branch vertex if the degree sum of any five independent vertices is at least n ? 2. These conditions are best possible. A related conjecture also is proposed.

By a 2-packing in a graph we mean a subset of its vertex set, in which all the vertices are in distance at least 3 from each other. The question about the maximum number of 2-packings in a graph is strongly related to the problem of L ( 2 , 1 ) -labeling of graphs. In this paper we find new asymptotic upper and lower bounds on the maximum number of 2-packings in a connected graph on n vertices. The bounds are O ( 1.5399 … n ) and Ω ( 1.4970 … n ) , respectively. Moreover, we present a lower bound on the number of k -element 2-packings in a connected graph, which is max ( n − 2 k + 2 k , ( k + 1 ) ⌊ n − 1 2 ⌋ k ) .

Graph separation and partitioning are fundamental problems that have been extensively studied both in theory and practice. The \textsc{$p$-Size Separator} problem, closely related to the \textsc{Balanced Separator} problem, is to check whether we can delete at most $k$ vertices in a given graph $G$ such that each connected component of the remaining graph has at most $p$ vertices. This problem is NP-hard for each fixed integer $p\geq 1$ and it becomes the famous \textsc{Vertex Cover} problem when $p=1$. It is known that the problem with parameter $k$ is W[1]-hard for unfixed $p$. In this paper, we prove a kernel of $O(pk)$ vertices for this problem, i.e., a linear vertex kernel for each fixed $p \geq 1$. In fact, we first obtain an $O(p^2k)$ vertex kernel by using a nontrivial extension of the expansion lemma. Then we further reduce the kernel size to $O(pk)$ by using some `local adjustment' techniques. Our proofs are based on extremal combinatorial arguments and the main result can be regarded as a generalization of the Nemhauser and Trotter's theorem for the \textsc{Vertex Cover} problem. These techniques are possible to be used to improve kernel sizes for more problems, especially problems with kernelization algorithms based on techniques similar to the expansion lemma or crown decompositions.

The metric dimension of a connected graph G is the minimum number of vertices in a subset S of the vertex set of G such that all other vertices are uniquely determined by their distances to the vertices in S. We define an extended metric dimension for graphs with some edges missing, which corresponds to the minimum number of vertices in a subset S such that all other vertices have unique distances to S in all minimally connected graphs that result from completing the original graph. This extension allows for incomplete knowledge of the underlying graph in applications such as localizing the source of infection. We give precise values for the extended metric dimension when the original graph's disconnected components are trees, cycles, grids, complete graphs, and we provide general upper bounds on this number in terms of the boundary of the graph.

The study of the phase transition of random graph processes, and recently in particular Achlioptas processes, has attracted much attention. Achlioptas, D'Souza and Spencer (Science, 2009) gave strong numerical evidence that a variety of edge-selection rules in Achlioptas processes exhibit a discontinuous phase transition. However, Riordan and Warnke (Science, 2011) recently showed that all these processes have a continuous phase transition.In this work we prove discontinuous phase transitions for three random graph processes: all three start with the empty graph on n vertices and, depending on the process, we connect in every step (i) one vertex chosen randomly from all vertices and one chosen randomly from a restricted set of vertices, (ii) two components chosen randomly from the set of all components, or (iii) a randomly chosen vertex and a randomly chosen component.

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.

For graphs $G$ and $H$, an $H$-coloring of $G$ is a function from the vertices of $G$ to the vertices of $H$ that preserves adjacency. $H$-colorings encode graph theory notions such as independent sets and proper colorings, and are a natural setting for the study of hard-constraint models in statistical physics. We study the set of $H$-colorings of the even discrete torus ${\mathbb Z}^d_m$, the graph on vertex set ${0, ..., m-1}^d$ ($m$ even) with two strings adjacent if they differ by 1 (mod $m$) on one coordinate and agree on all others. This is a bipartite graph, with bipartition classes ${\mathcal E}$ and ${\mathcal O}$. In the case $m=2$ the even discrete torus is the discrete hypercube or Hamming cube $Q_d$, the usual nearest neighbor graph on ${0,1}^d$. We obtain, for any $H$ and fixed $m$, a structural characterization of the space of $H$-colorings of ${\mathbb Z}^d_m$. We show that it may be partitioned into an exceptional subset of negligible size (as $d$ grows) and a collection of subsets indexed by certain pairs $(A,B) \in V(H)^2$, with each $H$-coloring in the subset indexed by $(A,B)$ having all but a vanishing proportion of vertices from ${\mathcal E}$ mapped to vertices from $A$, and all but a vanishing proportion of vertices from ${\mathcal O}$ mapped to vertices from $B$. This implies a long-range correlation phenomenon for uniformly chosen $H$-colorings of ${\mathbb Z}^d_m$ with $m$ fixed and $d$ growing. Our proof proceeds through an analysis of the entropy of a uniformly chosen $H$-coloring, and extends an approach of Kahn, who had considered the special case of $m=2$ and $H$ a doubly infinite path. All our results generalize to a natural weighted model of $H$-colorings., 29 pages, some corrections and minor revisions from earlier version, this version to appear in Journal of Combinatorial Theory Series B

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

A strong edge coloring of a graph G is an assignment of colors to the edges of G such that two distinct edges are colored differently if their distance is at most two. The strong chromatic index of a graph G, denoted by [email protected]^'(G), is the minimum number of colors needed for a strong edge coloring of G. A Halin graph G is a plane graph constructed from a tree T without vertices of degree two by connecting all leaves through a cycle C. If a Halin graph [email protected]?C is different from a certain necklace Ne"2 and any wheel W"n, [email protected]?0(mod3), then we prove that [email protected]^'(G)=

byremovinganykverticescontainsG.k-vertexextension of a graph G with n+k vertices is called minimal if among all k-vertex extensions of G with n+k vertices it has theminimalpossiblenumberofarcs.Westudydirectedgraphs,whoseminimalvertex1-extensionshaveaspecificnumberofadditionalarcs. A solution is given when the number of additional arcs equals one or two.Key words: minimal vertex extension, exact extension, fault tolerance, graph theory.

Let 2P"3 denote the disjoint union of two paths on three vertices. A graph G that has no subgraph isomorphic to a graph H is called H-free. The Vertex Coloring problem is the problem to determine the chromatic number of a graph. Its computational complexity for triangle-free H-free graphs has been classified for every fixed graph H on at most 6 vertices except for the case H=2P"3. This remaining case is posed as an open problem by Dabrowski, Lozin, Raman and Ries. We solve their open problem by showing polynomial-time solvability.

Given a claw-free graph and two non-adjacent vertices x and y without common neighbours we prove that there exists a hole through x and y unless the graph contains the obvious obstruction, namely a clique separating x and y. We derive two applications: We give a necessary and sufficient condition for the existence of an induced x-z path through y, where x,y,z are prescribed vertices in a claw-free graph; and we prove an induced version of [email protected]?s theorem between four terminal vertices. Finally, we improve the running time for detecting a hole through x and y and for the Three-in-a-Tree problem, if the input graph is claw-free.

A graph G has a tank-ring factor F if F is a connected spanning subgraph with all vertices of degree 2 or 4 that consists of one cycle C and disjoint triangles attaching to exactly one vertex of C such that every component of G − C contains exactly two vertices. In this paper, we show the following results. (1) Every supereulerian claw-free graph G with 1-hourglass property contains a tank-ring factor. (2) Every supereulerian claw-free graph with 2-hourglass property is Hamiltonian.

For a given graph H , a non-increasing sequence π = ( d 1 , d 2 , ? , d n ) of nonnegative integers is said to be potentially H -graphic if there exists a realization of π containing H as a subgraph. The split graph K r + K s ? on r + s vertices is denoted by S r , s . In this paper, we give a Rao-type characterization for π to be potentially S r , s -graphic. A simplification of this characterization is also presented.

Let G be a planar graph with maximum degree Δ≥7 and without intersecting 3-cycles; that is, two cycles of length 3 are not incident with a common vertex. Then the total chromatic number of G is Δ+1.

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.

We give a complete characterization of trees with at most four non-leave vertices, which factorize the complete graph K 2n .

A graph has thickness t if the edges can be decomposed into t and no fewer planar layers. We study one aspect of a generalization of Ringel's famous Earth-Moon problem: what is the largest chromatic number of any thickness-2 graph? In particular, given a graph G we consider the r-inflation of G and find bounds on both the thickness and the chromatic number of the inflated graphs. In some instances, the best possible bounds on both the chromatic number and thickness are achieved. We end with several open problems.

The length of a longest cycle in a graph G is called the circumference of G and is denoted by c(G). Let c(n)=min{c(G):G is a 3-connected cubic planar graph of order n}. Tait conjectured in 1884 that c(n)=n, and Tutte disproved this in 1946 by showing that c(n)≤n−1 for n=46. We prove that the inequality c(n)≤n−n+494+52 holds for infinitely many integers n. The exact value of c(n) is unknown.

Let G be a finite undirected graph with vertex set V(G). If [email protected]?V(G), let N[v] denote the closed neighbourhood of v, i.e. v itself and all its adjacent vertices in G. An identifying code in G is a subset C of V(G) such that the sets N[v]@?C are nonempty and pairwise distinct for each vertex [email protected]?V(G). We consider the problem of finding the minimum size of an identifying code in a given graph, which is known to be NP-hard. We give a linear algorithm that solves it in the class of trees, but show that the problem remains NP-hard in the class of planar graphs with arbitrarily large girth.

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. In this paper, we show that if G is a @?3k/2@?-connected graph of order n>=100k, and d(u)+d(v)>=n for any two vertices u and v with d(u,v)=2, then G is k-ordered hamiltonian. Our result implies the theorem of G. Chen et al. [Ars Combin. 70 (2004) 245-255] [1], which requires the degree sum condition for all pairs of non-adjacent vertices, not just those distance 2 apart.

For a nontrivial connected graph G, let $${c: V(G)\to {{\mathbb N}}}$$be a vertex coloring of G, where adjacent vertices may be colored the same. For a vertex v of G, let N(v) denote the set of vertices adjacent to v. The color sum σ(v) of v is the sum of the colors of the vertices in N(v). If σ(u) ≠ σ(v) for every two adjacent vertices u and v of G, then c is called a sigma coloring of G. The minimum number of colors required in a sigma coloring of a graph G is called its sigma chromatic number σ(G). The sigma chromatic number of a graph G never exceeds its chromatic number χ(G) and for every pair a, b of positive integers with a ≤ b, there exists a connected graph G with σ(G) = a and χ(G) = b. There is a connected graph G of order n with σ(G) = k for every pair k, n of positive integers with k ≤n if and only if k ≠ n − 1. Several other results concerning sigma chromatic numbers are presented.

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.