Semi-topological classification of line patterns in the plane
Sense Preserving Groups of Polyhedral Graphs.
Sensor Location Problem for a Multigraph
MSC 2010: 05C50, 15A03, 15A06, 65K05, 90C08, 90C35We introduce sparse linear underdetermined systems with embedded network structure. Their structure is inherited from the non-homogeneous network ow programming problems with nodes of variable intensities. One of the new applications of the researched underdetermined systems is the sensor location problem (SLP) for a multigraph. That is the location of the minimum number of sensors in the nodes of the multigraph, in order to determine the arcs ow...
Separability number and Schurity number of coherent configurations.
Separating plane convex sets.
Sequences of dominating sets.
Sequences of Maximal Degree Vertices in Graphs
2000 Mathematics Subject Classification: 05C35.Let Γ(M ) where M ⊂ V (G) be the set of all vertices of the graph G adjacent to any vertex of M. If v1, . . . , vr is a vertex sequence in G such that Γ(v1, . . . , vr ) = ∅ and vi is a maximal degree vertex in Γ(v1, . . . , vi−1), we prove that e(G) ≤ e(K(p1, . . . , pr)) where K(p1, . . . , pr ) is the complete r-partite graph with pi = |Γ(v1, . . . , vi−1) Γ(vi )|.
Sequentially perfect and uniform one-factorizations of the complete graph.
Series-parallel graphs and well- and better-quasi-orderings
Set colorings in perfect graphs
For a nontrivial connected graph , let be a vertex coloring of where adjacent vertices may be colored the same. For a vertex , the neighborhood color set is the set of colors of the neighbors of . The coloring is called a set coloring if for every pair of adjacent vertices of . The minimum number of colors required of such a coloring is called the set chromatic number . We show that the decision variant of determining is NP-complete in the general case, and show that can be...
Set vertex colorings and joins of graphs
For a nontrivial connected graph , let be a vertex coloring of where adjacent vertices may be colored the same. For a vertex of , the neighborhood color set is the set of colors of the neighbors of . The coloring is called a set coloring if for every pair of adjacent vertices of . The minimum number of colors required of such a coloring is called the set chromatic number . A study is made of the set chromatic number of the join of two graphs and . Sharp lower and upper bounds...
Sets with two associative operations
In this paper we consider duplexes, which are sets with two associative binary operations. Dimonoids in the sense of Loday are examples of duplexes. The set of all permutations carries a structure of a duplex. Our main result asserts that it is a free duplex with an explicitly described set of generators. The proof uses a construction of the free duplex with one generator by planary trees.
Set-systems with restricted multiple intersections.
Several results on chordal bipartite graphs
The question of generalizing results involving chordal graphs to similar concepts for chordal bipartite graphs is addressed. First, it is found that the removal of a bisimplicial edge from a chordal bipartite graph produces a chordal bipartite graph. As consequence, occurance of arithmetic zeros will not terminate perfect Gaussian elimination on sparse matrices having associated a chordal bipartite graph. Next, a property concerning minimal edge separators is presented. Finally, it is shown that,...
Shadow trees of Mandelbrot sets
The topology and combinatorial structure of the Mandelbrot set (of degree d ≥ 2) can be studied using symbolic dynamics. Each parameter is mapped to a kneading sequence, or equivalently, an internal address; but not every such sequence is realized by a parameter in . Thus the abstract Mandelbrot set is a subspace of a larger, partially ordered symbol space, . In this paper we find an algorithm to construct “visible trees” from symbolic sequences which works whether or not the sequence is realized....
Sharp bounds for the number of matchings in generalized-theta-graphs
A generalized-theta-graph is a graph consisting of a pair of end vertices joined by k (k ≥ 3) internally disjoint paths. We denote the family of all the n-vertex generalized-theta-graphs with k paths between end vertices by Θⁿₖ. In this paper, we determine the sharp lower bound and the sharp upper bound for the total number of matchings of generalized-theta-graphs in Θⁿₖ. In addition, we characterize the graphs in this class of graphs with respect to the mentioned bounds.
Sharp bounds for the sum of the squares of the degrees of a graph
Sharp edge-homotopy on spatial graphs.
A sharp-move is known as an unknotting operation for knots. A self sharp-move is a sharp-move on a spatial graph where all strings in the move belong to the same spatial edge. We say that two spatial embeddings of a graph are sharp edge-homotopic if they are transformed into each other by self sharp-moves and ambient isotopies. We investigate how is the sharp edge-homotopy strong and classify all spatial theta curves completely up to sharp edge-homotopy. Moreover we mention a relationship between...
Sharp sufficient conditions for Hamiltonian cycles in tough graphs
Sharp threshold functions for random intersection graphs via a coupling method.