EuDML | Browse

Items

All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Displaying 181 – 200 of 376

Light classes of generalized stars in polyhedral maps on surfaces

Stanislav Jendrol', Heinz-Jürgen Voss (2004)

Discussiones Mathematicae Graph Theory

A generalized s-star, s ≥ 1, is a tree with a root Z of degree s; all other vertices have degree ≤ 2. $S_{i}$ denotes a generalized 3-star, all three maximal paths starting in Z have exactly i+1 vertices (including Z). Let be a surface of Euler characteristic χ() ≤ 0, and m():= ⎣(5 + √49-24χ( ))/2⎦. We prove: (1) Let k ≥ 1, d ≥ m() be integers. Each polyhedral map G on with a k-path (on k vertices) contains a k-path of maximum degree ≤ d in G or a generalized s-star T, s ≤ m(), on d + 2- m() vertices...

Locally $C_{n}^{k}$ graphs.

Buset, Dominique (1995)

Bulletin of the Belgian Mathematical Society - Simon Stevin

Locally regular graphs

Bohdan Zelinka (2000)

Mathematica Bohemica

A graph $G$ is called locally $s$ -regular if the neighbourhood of each vertex of $G$ induces a subgraph of $G$ which is regular of degree $s$ . We study graphs which are locally $s$ -regular and simultaneously regular of degree $r$ .

Matrix partitions with finitely many obstructions.

Feder, Tomás, Hell, Pavol, Xie, Wing (2007)

The Electronic Journal of Combinatorics [electronic only]

Maxclique and Unit Disk Characterizations of Strongly Chordal Graphs

Pablo De Caria, Terry A. McKee (2014)

Discussiones Mathematicae Graph Theory

Maxcliques (maximal complete subgraphs) and unit disks (closed neighborhoods of vertices) sometime play almost interchangeable roles in graph theory. For instance, interchanging them makes two existing characterizations of chordal graphs into two new characterizations. More intriguingly, these characterizations of chordal graphs can be naturally strengthened to new characterizations of strongly chordal graphs

Maximal graphs with respect to hereditary properties

Izak Broere, Marietjie Frick, Gabriel Semanišin (1997)

Discussiones Mathematicae Graph Theory

A property of graphs is a non-empty set of graphs. A property P is called hereditary if every subgraph of any graph with property P also has property P. Let P₁, ...,Pₙ be properties of graphs. We say that a graph G has property P₁∘...∘Pₙ if the vertex set of G can be partitioned into n sets V₁, ...,Vₙ such that the subgraph of G induced by Vi has property $P_{i}$ ; i = 1,..., n. A hereditary property R is said to be reducible if there exist two hereditary properties P₁ and P₂ such that R = P₁∘P₂. If P...

Maximum degree growth of the iterated line graph.

Hartke, Stephen G., Higgins, Aparna W. (1999)

The Electronic Journal of Combinatorics [electronic only]

Median and quasi-median direct products of graphs

Boštjan Brešar, Pranava K. Jha, Sandi Klavžar, Blaž Zmazek (2005)

Discussiones Mathematicae Graph Theory

Median graphs are characterized among direct products of graphs on at least three vertices. Beside some trivial cases, it is shown that one component of G×P₃ is median if and only if G is a tree in that the distance between any two vertices of degree at least 3 is even. In addition, some partial results considering median graphs of the form G×K₂ are proved, and it is shown that the only nonbipartite quasi-median direct product is K₃×K₃.

Median properties of graphs with small diameters

Bohdan Zelinka (1995)

Mathematica Bohemica

Two numerical invariants $Δ (G)$ and $Γ (G)$ of a graph, related to the concept of median, are studied.

Minimal claw-free graphs

P. Dankelmann, Henda C. Swart, P. van den Berg, Wayne Goddard, M. D. Plummer (2008)

Czechoslovak Mathematical Journal

A graph $G$ is a minimal claw-free graph (m.c.f. graph) if it contains no $K_{1, 3}$ (claw) as an induced subgraph and if, for each edge $e$ of $G$ , $G - e$ contains an induced claw. We investigate properties of m.c.f. graphs, establish sharp bounds on their orders and the degrees of their vertices, and characterize graphs which have m.c.f. line graphs.

Minimal cycle bases of the lexicographic product of graphs

M.M.M. Jaradat (2008)

Discussiones Mathematicae Graph Theory

A construction of minimum cycle bases of the lexicographic product of graphs is presented. Moreover, the length of a longest cycle of a minimal cycle basis is determined.

Minimal trees and monophonic convexity

Jose Cáceres, Ortrud R. Oellermann, M. L. Puertas (2012)

Discussiones Mathematicae Graph Theory

Let V be a finite set and 𝓜 a collection of subsets of V. Then 𝓜 is an alignment of V if and only if 𝓜 is closed under taking intersections and contains both V and the empty set. If 𝓜 is an alignment of V, then the elements of 𝓜 are called convex sets and the pair (V,𝓜 ) is called an alignment or a convexity. If S ⊆ V, then the convex hull of S is the smallest convex set that contains S. Suppose X ∈ ℳ. Then x ∈ X is an extreme point for X if X∖{x} ∈ ℳ. A convex geometry on a finite set is...

Modular and median signpost systems and their underlying graphs

Henry Martyn Mulder, Ladislav Nebeský (2003)

Discussiones Mathematicae Graph Theory

The concept of a signpost system on a set is introduced. It is a ternary relation on the set satisfying three fairly natural axioms. Its underlying graph is introduced. When the underlying graph is disconnected some unexpected things may happen. The main focus are signpost systems satisfying some extra axioms. Their underlying graphs have lots of structure: the components are modular graphs or median graphs. Yet another axiom guarantees that the underlying graph is also connected. The main results...

More forbidden minors for wye-delta-wye reducibility.

Yu, Yaming (2006)

The Electronic Journal of Combinatorics [electronic only]

More on even [a,b]-factors in graphs

Abdollah Khodkar, Rui Xu (2007)

Discussiones Mathematicae Graph Theory

In this note we give a characterization of the complete bipartite graphs which have an even (odd) [a,b]-factor. For general graphs we prove that an a-edge connected graph G with n vertices and with δ(G) ≥ max{a+1,an/(a+b) + a - 2} has an even [a,b]-factor, where a and b are even and 2 ≤ a ≤ b. With regard to the edge-connectivity this result is slightly better than one of the similar results obtained by Kouider and Vestergaard in 2004 and unlike their results, this result has no restriction on the...

Natural bijections between directed and undirected self-complementary graphs

Bohdan Zelinka (1987)

Mathematica Slovaca

Nearly acyclic digraphs

Bohdan Zelinka (1983)

Czechoslovak Mathematical Journal

Neighbourhoods in line graphs

Ľubomír Šoltés (1992)

Mathematica Slovaca

New edge neighborhood graphs

Ali A. Ali, Salar Y. Alsardary (1997)

Czechoslovak Mathematical Journal

Let $G$ be an undirected simple connected graph, and $e = u v$ be an edge of $G$ . Let $N_{G} (e)$ be the subgraph of $G$ induced by the set of all vertices of $G$ which are not incident to $e$ but are adjacent to $u$ or $v$ . Let $𝒩_{e}$ be the class of all graphs $H$ such that, for some graph $G$ , $N_{G} (e) ≅ H$ for every edge $e$ of $G$ . Zelinka [3] studied edge neighborhood graphs and obtained some special graphs in $𝒩_{e}$ . Balasubramanian and Alsardary [1] obtained some other graphs in $𝒩_{e}$ . In this paper we given some new graphs in $𝒩_{e}$ .

New proof of a characterization of geodetic graphs

Ladislav Nebeský (2002)

Czechoslovak Mathematical Journal

In [3], the present author used a binary operation as a tool for characterizing geodetic graphs. In this paper a new proof of the main result of the paper cited above is presented. The new proof is shorter and simpler.

Currently displaying 181 – 200 of 376

Previous Page 10 Next