It is proved that for every integer $k\ge3$, for every (simple) series-parallel graph $G$ with maximum degree at most $k$, and for every collection $(L(e):e\in E(G))$ of sets, each of size at least ...$k$, there exists a proper edge-coloring of $G$ such that for every edge $e\in E(G)$, the color of $e$ belongs to $L(e)$.
Let
K be a subgraph of
G. Suppose that we have a 2-cell embedding of
K in some surface and that for each
K-bridge in
G, one or two simple embeddings in faces of
K are prescribed. Obstructions for ...existence of extensions of the embedding of
K to an embedding of
G are studied. It is shown that minimal obstructions possess certain combinatorial structure that can be described in an algebraic way by means of forcing chains of
K-bridges. The geometric structure of minimal obstructions is also described. It is shown that they have “millipede” structure that was observed earlier in some special cases (disc, Möbius band). As a consequence it is proved that if one is allowed to reroute the branches of
K, one can obtain a subgraph
K′ of
G homeomorphic to
K for which an obstruction of bounded branch size exists. The precise combinatorial and geometric structure of corresponding obstructions can be used to get a linear time algorithm for either finding an embedding extension or discovering minimal obstructions.
For several NP-hard optimal linear labeling problems, including the bandwidth, the cutwidth, and the min-sum problem for graphs, a heuristic algorithm is proposed which finds approximative solutions ...to these problems in polynomial time. The algorithm uses eigenvectors corresponding to the second smallest Laplace eigenvalue of a graph. Although bad in some “degenerate” cases, the algorithm shows fairly good behaviour. Several upper and lower bounds on the bandwidth, cutwidth, and min-
p-sums are derived. Most of these bounds are given in terms of Laplace eigenvalues of the graphs. They are used in the analysis of our algorithm and as measures for the error of the obtained approximation to an optimal labeling.
Distance-related invariants on polygraphs Juvan, Martin; Mohar, Bojan; Žerovnik, Janez
Discrete Applied Mathematics,
12/1997, Letnik:
80, Številka:
1
Journal Article
Recenzirano
Odprti dostop
Let
M
(
n)
be a graph which is obtained from a path
P
n
or a cycle
C
n
by replacing each vertex by a fixed graph
M and replacing each edge by a fixed set of edges joining the corresponding copies of
...M. A matrix approach to the computation of distance-related invariants in such graphs is presented. This approach gives a general procedure to obtain closed formulas (depending on
n) for such invariants of
M
(
n)
. As an example, the Wiener index is treated in more detail.
In this paper we study list edge-colorings of graphs with small maximal degree. In particular, we show that simple subcubic graphs are ‘10/3-edge choosable’. The precise meaning of this statement is ...that no matter how we prescribe arbitrary lists of three colors on edges of a subgraph
H of
G such that Δ(
H)⩽2, and prescribe lists of four colors on
E(G)∖E(H), the subcubic graph
G will have an edge-coloring with the given colors. Several consequences follow from this result.
Let $K=C\cup e_1\cup e_2$ be a subgraph of G consisting of a cycle C and disjoint paths e1 and e2 connecting two interlacing pairs of vertices in C. Suppose that K is embedded in the Mobius band in ...such a way that C lies on its boundary. An algorithm is presented which in linear time extends the embedding of K to an embedding of G, if such an extension is possible, or finds a "nice" obstruction for such embedding extensions. The structure of obtained obstructions is also analyzed in detail.
Bond Contributions to the Wiener Index Juvan, Martin; Mohar, Bojan
Journal of chemical information and computer sciences,
03/1995, Letnik:
35, Številka:
2
Journal Article
An algorithm for computing the algebraic structure count in polygraphs is presented. It expresses the related determinant of the adjacency matrix of a polygraph in terms of the determinants of ...monographs and bonding edges between the monographs. The algorithm is illustrated on a class of polygraphs with two bonding edges between monographs and computations for selected examples of polygraphs of this class are presented.
PDF
