Asymmetrische reguläre Graphen

Ohne Zusammenfassung     

NZ‐flows in strong products of graphs

We prove that the strong product G₁? G₂ of G₁ and G₂ is ?₃‐flow contractible if and only if G₁? G₂ is not T? K₂, where T is a tree (we call T? K₂ a K₄‐tree). It follows that G₁? G₂ admits an NZ 3 ‐flow unless G₁? G₂ is a K₄ ‐tree. We also give a constructive proof that yields a polynomial algorithm whose output is an NZ 3‐flow if G₁? G₂ is not a K₄ ‐tree, and an NZ 4‐flow otherwise. © 2009 Wiley Periodicals, Inc. J Graph Theory 64: 267–276, 2010     

Antibandwidth and cyclic antibandwidth of meshes and hypercubes

The antibandwidth problem consists of placing the vertices of a graph on a line in consecutive integer points in such a way that the minimum difference of adjacent vertices is maximised. The problem was originally introduced in [J.Y.-T. Leung, O. Vornberger, J.D. Witthoff, On some variants of the bandwidth minimisation problem, SIAM Journal of Computing 13 (1984) 650-667] in connection with the multiprocessor scheduling problems and can also be understood as a dual problem to the well-known bandwidth problem, as a special radiocolouring problem or as a variant of obnoxious facility location problems. The antibandwidth problem is NP-hard, there are a few classes of graphs with polynomial time complexities. Exact results for nontrivial graphs are very rare. Miller and Pritikin [Z. Miller, D. Pritikin, On the separation number of a graph, Networks 19 (1989) 651-666] showed tight bounds for the two-dimensional meshes and hypercubes. We solve the antibandwidth problem precisely for two-dimensional meshes, tori and estimate the antibandwidth value for hypercubes up to the third-order term. The cyclic antibandwidth problem is to embed an n-vertex graph into the cycle C_n, such that the minimum distance (measured in the cycle) of adjacent vertices is maximised. This is a natural extension of the antibandwidth problem or a dual problem to the cyclic bandwidth problem. We start investigating this invariant for typical graphs and prove basic facts and exact results for the same product graphs as for the antibandwidth.     

Tautomerism,regioisomerism, and cyclization reactions of acridinyl thiosemicarbazides

The regioselectivities of methyl‐ and phenylhydrazine with acridin‐9‐yl isothiocyanate (thus yielding thiosemicarbazides with acridine substituted on the urea‐type side) were examined. Methylhydrazine regioselectivity was high with the α‐nitrogen atom overwhelmingly more nucleophilic than the β‐nitrogen atom; phenylhydrazine regioselectivity was poor but varied with the solvent and only in the case of ethanol was nucleophilic predominance of the α‐nitrogen atom pronounced. Of note, whilst both phenyl thiosemicarbazides were present in solution only as spiro forms, the methyl product was present as an equilibrium mixture of open‐chain and spiro thiosemicarbazides. Reactions on the NH₂ blocked analogue of methyl acridin‐9‐ylthiosemicarbazide (1‐isopropylidene‐2‐methylthiosemicarbazide) were also examined. Interestingly, present in the starting material itself was a structural motif of novelty wherein a triazolethione represented the major species of an equilibrium between cyclic and open‐chain forms.     

Unusual structures derived from N‐acridin‐9‐yl methyl N′‐acridin‐9‐yl thiourea based on the propensity of N‐10 to retain H

N‐Acridin‐9‐yl methyl N′‐acridin‐9‐yl thiourea spontaneously spiro cyclises via nucleophilic attack of the methylene carbon onto the C‐9 of the other acridine moiety. The thiourea, upon reaction with bromoacetonitrile, provided a spiro fused‐bicyclic product displaying unusual dynamic behavior.