Random threshold graphs.
Displaying 61 – 80 of 84
Realization of Hölder complexes
Lev Birbrair, Marina Sobolevsky (1999)
Annales de la Faculté des sciences de Toulouse : Mathématiques
Simultaneous graph drawing: layout algorithms and visualization schemes.
Erten, C., Kobourov, S.G., Le, V., Navabi, A. (2005)
Journal of Graph Algorithms and Applications
Some news about oblique graphs
Andrey A. Dobrynin, Leonid S. Melnikov, Jens Schreyer, Hansjoachim Walther (2002)
Discussiones Mathematicae Graph Theory
A k-gon α of a polyhedral graph G(V,E,F) is of type ⟨b₁,b₂,...,bₖ⟩ if the vertices incident with α in cyclic order have degrees b₁,b₂,...,bₖ and ⟨b₁,b₂,...,bₖ⟩ is the lexicographic minimum of all such sequences available for α. A polyhedral graph G is oblique if it has no two faces of the same type. Among others it is shown that an oblique graph contains vertices of degree 3.
Some Variations of Perfect Graphs
Magda Dettlaff, Magdalena Lemańska, Gabriel Semanišin, Rita Zuazua (2016)
Discussiones Mathematicae Graph Theory
We consider (ψk−γk−1)-perfect graphs, i.e., graphs G for which ψk(H) = γk−1(H) for any induced subgraph H of G, where ψk and γk−1 are the k-path vertex cover number and the distance (k − 1)-domination number, respectively. We study (ψk−γk−1)-perfect paths, cycles and complete graphs for k ≥ 2. Moreover, we provide a complete characterisation of (ψ2 − γ1)- perfect graphs describing the set of its forbidden induced subgraphs and providing the explicit characterisation of the structure of graphs belonging...
Spatial graphs, knots and the cyclic polytope.
Alfonsí, J.L.Ramírez (2008)
Beiträge zur Algebra und Geometrie
Splitting Cubic Circle Graphs
Lorenzo Traldi (2016)
Discussiones Mathematicae Graph Theory
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.
Stacks, queues and tracks: layouts of graph subdivisions.
Dujmović, Vida, Wood, David R. (2005)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Straight-line drawings of binary trees with linear area and arbitrary aspect ratio.
Garg, Ashim, Rusu, Adrian (2004)
Journal of Graph Algorithms and Applications
Straight-line drawings on restricted integer grids in two and three dimensions.
Felsner, Stefan, Liotta, Giuseppe, Wismath, Stephen (2003)
Journal of Graph Algorithms and Applications
Strictly convex drawings of planar graphs.
Bárány, Imre, Rote, Günter (2006)
Documenta Mathematica
Strongly pancyclic and dual-pancyclic graphs
Terry A. McKee (2009)
Discussiones Mathematicae Graph Theory
Say that a cycle C almost contains a cycle C¯ if every edge except one of C¯ is an edge of C. Call a graph G strongly pancyclic if every nontriangular cycle C almost contains another cycle C¯ and every nonspanning cycle C is almost contained in another cycle C⁺. This is equivalent to requiring, in addition, that the sizes of C¯ and C⁺ differ by one from the size of C. Strongly pancyclic graphs are pancyclic and chordal, and their cycles enjoy certain interpolation and extrapolation properties with...
Symmetry of iteration graphs
Walter Carlip, Martina Mincheva (2008)
Czechoslovak Mathematical Journal
We examine iteration graphs of the squaring function on the rings when , for a Fermat prime. We describe several invariants associated to these graphs and use them to prove that the graphs are not symmetric when and when and are symmetric when .
The arc-width of a graph.
Barát, János, Hajnal, Péter (2001)
The Electronic Journal of Combinatorics [electronic only]
The cost chromatic number and hypergraph parameters
Gábor Bacsó, Zsolt Tuza (2006)
Discussiones Mathematicae Graph Theory
In a graph, by definition, the weight of a (proper) coloring with positive integers is the sum of the colors. The chromatic sum is the minimum weight, taken over all the proper colorings. The minimum number of colors in a coloring of minimum weight is the cost chromatic number or strength of the graph. We derive general upper bounds for the strength, in terms of a new parameter of representations by edge intersections of hypergraphs.
The crossing number of a projective graph is quadratic in the face-width.
Gitler, I., Hlineny, P., Leaños, J., Salazar, G. (2008)
The Electronic Journal of Combinatorics [electronic only]
The maximum number of edges in a three-dimensional grid-drawing.
Bose, Prosenjit, Czyzowicz, Jurek, Morin, Pat, Wood, David R. (2004)
Journal of Graph Algorithms and Applications
The representation of multi-hypergraphs by set intersections
Stanisław Bylka, Jan Komar (2007)
Discussiones Mathematicae Graph Theory
This paper deals with weighted set systems (V,,q), where V is a set of indices, and the weight q is a nonnegative integer function on . The basic idea of the paper is to apply weighted set systems to formulate restrictions on intersections. It is of interest to know whether a weighted set system can be represented by set intersections. An intersection representation of (V,,q) is defined to be an indexed family of subsets of a set S such that for each E ∈ . A necessary condition for the existence...
The restricted arc-width of a graph.
Arthur, David (2003)
The Electronic Journal of Combinatorics [electronic only]
The structure of plane graphs with independent crossings and its applications to coloring problems
Xin Zhang, Guizhen Liu (2013)
Open Mathematics
If a graph G has a drawing in the plane in such a way that every two crossings are independent, then we call G a plane graph with independent crossings or IC-planar graph for short. In this paper, the structure of IC-planar graphs with minimum degree at least two or three is studied. By applying their structural results, we prove that the edge chromatic number of G is Δ if Δ ≥ 8, the list edge (resp. list total) chromatic number of G is Δ (resp. Δ + 1) if Δ ≥ 14 and the linear arboricity of G is...