Spectrally arbitrary tree sign patterns of order 4.
Spectrum Of The Total Graph Of A Graph
Spectrum of two new joins of graphs and infinite families of integral graphs
Spherical and clockwise spherical graphs
The main subject of our study are spherical (weakly spherical) graphs, i.e. connected graphs fulfilling the condition that in each interval to each vertex there is exactly one (at least one, respectively) antipodal vertex. Our analysis concerns properties of these graphs especially in connection with convexity and also with hypercube graphs. We deal e.g. with the problem under what conditions all intervals of a spherical graph induce hypercubes and find a new characterization of hypercubes: is...
Splitting Cubic Circle Graphs
We show that every 3-regular circle graph has at least two pairs of twin vertices; consequently no such graph is prime with respect to the split decomposition. We also deduce that up to isomorphism, K4 and K3,3 are the only 3-connected, 3-regular circle graphs.
Square-root rule of two-dimensional bandwidth problem
The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root...
Square-root rule of two-dimensional bandwidth problem∗
The bandwidth minimization problem is of significance in network communication and related areas. Let G be a graph of n vertices. The two-dimensional bandwidth B2(G) of G is the minimum value of the maximum distance between adjacent vertices when G is embedded into an n × n grid in the plane. As a discrete optimization problem, determining B2(G) is NP-hard in general. However, exact results for this parameter can be derived for some special classes of graphs. This paper studies the “square-root...
Squares of triangular cacti
Square-stable and well-covered graphs.
Stability of graphs.
Stable graphs
Stable rational cohomology of automorphism groups of free groups and the integral cohomology of moduli spaces of graphs.
It is not known whether or not the stable rational cohomology groups H*(Aut(F∞);Q) always vanish (see Hatcher in [5] and Hatcher and Vogtmann in [7] where they pose the question and show that it does vanish in the first 6 dimensions). We show that either the rational cohomology does not vanish in certain dimensions, or the integral cohomology of a moduli space of pointed graphs does not stabilize in certain other dimensions. Similar results are stated for groups of outer automorphisms. This yields...
Stable sets for -free graphs
The Maximum Stable Set (MS) problem is a well known NP-hard problem. However different graph classes for which MS can be efficiently solved have been detected and the augmenting graph technique seems to be a fruitful tool to this aim. In this paper we apply a recent characterization of minimal augmenting graphs [22] to prove that MS can be solved for -free graphs in polynomial time, extending some known results.
Stacks, queues and tracks: layouts of graph subdivisions.
Star coloring high girth planar graphs.
Star Coloring of Subcubic Graphs
A star coloring of an undirected graph G is a coloring of the vertices of G such that (i) no two adjacent vertices receive the same color, and (ii) no path on 4 vertices is bi-colored. The star chromatic number of G, χs(G), is the minimum number of colors needed to star color G. In this paper, we show that if a graph G is either non-regular subcubic or cubic with girth at least 6, then χs(G) ≤ 6, and the bound can be realized in linear time.
Star Complements and Maximal Exceptional Graphs
Star number and star arboricity of a complete multigraph
Let be a multigraph. The star number of is the minimum number of stars needed to decompose the edges of . The star arboricity of is the minimum number of star forests needed to decompose the edges of . As usual denote the -fold complete graph on vertices (i.e., the multigraph on vertices such that there are edges between every pair of vertices). In this paper, we prove that for
Star-Cycle Factors of Graphs
A spanning subgraph F of a graph G is called a star-cycle factor of G if each component of F is a star or cycle. Let G be a graph and f : V (G) → {1, 2, 3, . . .} be a function. Let W = {v ∈ V (G) : f(v) = 1}. Under this notation, it was proved by Berge and Las Vergnas that G has a star-cycle factor F with the property that (i) if a component D of F is a star with center v, then degF (v) ≤ f(v), and (ii) if a component D of F is a cycle, then V (D) ⊆ W if and only if iso(G − S) ≤ Σx∈S f(x) for all...
Starlike trees with maximum degree 4 are determined by their signless Laplacian spectra.