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

Previous Page 2 Next

Displaying 21 – 40 of 71

Showing per page

On graphs with maximum size in their switching classes

Sergiy Kozerenko (2015)

Commentationes Mathematicae Universitatis Carolinae

In his PhD thesis [Structural aspects of switching classes, Leiden Institute of Advanced Computer Science, 2001] Hage posed the following problem: “characterize the maximum size graphs in switching classes”. These are called s-maximal graphs. In this paper, we study the properties of such graphs. In particular, we show that any graph with sufficiently large minimum degree is s-maximal, we prove that join of two s-maximal graphs is also an s-maximal graph, we give complete characterization of triangle-free...

On hereditary properties of composition graphs

Vadim E. Levit, Eugen Mandrescu (1998)

Discussiones Mathematicae Graph Theory

The composition graph of a family of n+1 disjoint graphs H i : 0 ≤ i ≤ n is the graph H obtained by substituting the n vertices of H₀ respectively by the graphs H₁,H₂,...,Hₙ. If H has some hereditary property P, then necessarily all its factors enjoy the same property. For some sort of graphs it is sufficient that all factors H i : 0 ≤ i ≤ n have a certain common P to endow H with this P. For instance, it is known that the composition graph of a family of perfect graphs is also a perfect graph (B. Bollobas, 1978), and the...

On infinite outerplanar graphs

Luis B. Boza, Ana Diánez, Alberto Márquez (1994)

Mathematica Bohemica

In this Note, we study infinite graphs with locally finite outerplane embeddings, given a characterization by forbidden subgraphs.

On infinite uniquely partitionable graphs and graph properties of finite character

Jozef Bucko, Peter Mihók (2009)

Discussiones Mathematicae Graph Theory

A graph property is any nonempty isomorphism-closed class of simple (finite or infinite) graphs. A graph property is of finite character if a graph G has a property if and only if every finite induced subgraph of G has a property . Let ₁,₂,...,ₙ be graph properties of finite character, a graph G is said to be (uniquely) (₁, ₂, ...,ₙ)-partitionable if there is an (exactly one) partition V₁, V₂, ..., Vₙ of V(G) such that G [ V i ] ∈ i for i = 1,2,...,n. Let us denote by ℜ = ₁ ∘ ₂ ∘ ... ∘ ₙ the class of all (₁,₂,...,ₙ)-partitionable...

On k -pairable graphs from trees

Zhongyuan Che (2007)

Czechoslovak Mathematical Journal

The concept of the k -pairable graphs was introduced by Zhibo Chen (On k -pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter p ( G ) , called the pair length of a graph G , as the maximum k such that G is k -pairable and p ( G ) = 0 if G is not k -pairable for any positive integer k . In this paper, we answer the two open questions raised by Chen in the case that the graphs involved...

On light subgraphs in plane graphs of minimum degree five

Stanislav Jendrol', Tomáš Madaras (1996)

Discussiones Mathematicae Graph Theory

A subgraph of a plane graph is light if the sum of the degrees of the vertices of the subgraph in the graph is small. It is well known that a plane graph of minimum degree five contains light edges and light triangles. In this paper we show that every plane graph of minimum degree five contains also light stars K 1 , 3 and K 1 , 4 and a light 4-path P₄. The results obtained for K 1 , 3 and P₄ are best possible.

On •-Line Signed Graphs L•(S)

Deepa Sinha, Ayushi Dhama (2015)

Discussiones Mathematicae Graph Theory

A signed graph (or sigraph for short) is an ordered pair S = (Su,σ), where Su is a graph, G = (V,E), called the underlying graph of S and σ : E → {+,−} is a function from the edge set E of Su into the set {+,−}. For a sigraph S its •-line sigraph, L•(S) is the sigraph in which the edges of S are represented as vertices, two of these vertices are defined adjacent whenever the corresponding edges in S have a vertex in common, any such L-edge ee′ has the sign given by the product of the signs of the...

On magic and supermagic line graphs

Jaroslav Ivančo, Z. Lastivková, A. Semaničová (2004)

Mathematica Bohemica

A graph is called magic (supermagic) if it admits a labelling of the edges by pairwise different (consecutive) positive integers such that the sum of the labels of the edges incident with a vertex is independent of the particular vertex. We characterize magic line graphs of general graphs and describe some class of supermagic line graphs of bipartite graphs.

On Minimum (Kq, K) Stable Graphs

J.L. Fouquet, H. Thuillier, J.M. Vanherpe, A.P. Wojda (2013)

Discussiones Mathematicae Graph Theory

A graph G is a (Kq, k) stable graph (q ≥ 3) if it contains a Kq after deleting any subset of k vertices (k ≥ 0). Andrzej ˙ Zak in the paper On (Kq; k)-stable graphs, ( doi:/10.1002/jgt.21705) has proved a conjecture of Dudek, Szyma´nski and Zwonek stating that for sufficiently large k the number of edges of a minimum (Kq, k) stable graph is (2q − 3)(k + 1) and that such a graph is isomorphic to sK2q−2 + tK2q−3 where s and t are integers such that s(q − 1) + t(q − 2) − 1 = k. We have proved (Fouquet...

On partial cubes and graphs with convex intervals

Boštjan Brešar, Sandi Klavžar (2002)

Commentationes Mathematicae Universitatis Carolinae

A graph is called a partial cube if it admits an isometric embedding into a hypercube. Subdivisions of wheels are considered with respect to such embeddings and with respect to the convexity of their intervals. This allows us to answer in negative a question of Chepoi and Tardif from 1994 whether all bipartite graphs with convex intervals are partial cubes. On a positive side we prove that a graph which is bipartite, has convex intervals, and is not a partial cube, always contains a subdivision...

Currently displaying 21 – 40 of 71