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 5 Next

Displaying 81 – 100 of 8549

Showing per page

A Characterization of 2-Tree Probe Interval Graphs

David E. Brown, Breeann M. Flesch, J. Richard (2014)

Discussiones Mathematicae Graph Theory

A graph is a probe interval graph if its vertices correspond to some set of intervals of the real line and can be partitioned into sets P and N so that vertices are adjacent if and only if their corresponding intervals intersect and at least one belongs to P. We characterize the 2-trees which are probe interval graphs and extend a list of forbidden induced subgraphs for such graphs created by Pržulj and Corneil in [2-tree probe interval graphs have a large obstruction set, Discrete Appl. Math. 150...

A characterization of C 2 ( q ) where q > 5

Ali Iranmanesh, Behrooz Khosravi (2002)

Commentationes Mathematicae Universitatis Carolinae

The order of every finite group G can be expressed as a product of coprime positive integers m 1 , ⋯ , m t such that π ( m i ) is a connected component of the prime graph of G . The integers m 1 , ⋯ , m t are called the order components of G . Some non-abelian simple groups are known to be uniquely determined by their order components. As the main result of this paper, we show that the projective symplectic groups C 2 ( q ) where q > 5 are also uniquely determined by their order components. As corollaries of this result, the validities of a...

A characterization of complete tripartite degree-magic graphs

Ľudmila Bezegová, Jaroslav Ivančo (2012)

Discussiones Mathematicae Graph Theory

A graph is called degree-magic if it admits a labelling of the edges by integers 1, 2,..., |E(G)| such that the sum of the labels of the edges incident with any vertex v is equal to (1+ |E(G)|)/2*deg(v). Degree-magic graphs extend supermagic regular graphs. In this paper we characterize complete tripartite degree-magic graphs.

A characterization of diameter-2-critical graphs with no antihole of length four

Teresa Haynes, Michael Henning (2012)

Open Mathematics

A graph G is diameter-2-critical if its diameter is two and the deletion of any edge increases the diameter. In this paper we characterize the diameter-2-critical graphs with no antihole of length four, that is, the diameter-2-critical graphs whose complements have no induced 4-cycle. Murty and Simon conjectured that the number of edges in a diameter-2-critical graph of order n is at most n 2/4 and that the extremal graphs are complete bipartite graphs with equal size partite sets. As a consequence...

A Characterization of Hypergraphs with Large Domination Number

Michael A. Henning, Christian Löwenstein (2016)

Discussiones Mathematicae Graph Theory

Let H = (V, E) be a hypergraph with vertex set V and edge set E. A dominating set in H is a subset of vertices D ⊆ V such that for every vertex v ∈ V D there exists an edge e ∈ E for which v ∈ e and e ∩ D ≠ ∅. The domination number γ(H) is the minimum cardinality of a dominating set in H. It is known [Cs. Bujtás, M.A. Henning and Zs. Tuza, Transversals and domination in uniform hypergraphs, European J. Combin. 33 (2012) 62-71] that for k ≥ 5, if H is a hypergraph of order n and size m with all...

A characterization of locating-total domination edge critical graphs

Mostafa Blidia, Widad Dali (2011)

Discussiones Mathematicae Graph Theory

For a graph G = (V,E) without isolated vertices, a subset D of vertices of V is a total dominating set (TDS) of G if every vertex in V is adjacent to a vertex in D. The total domination number γₜ(G) is the minimum cardinality of a TDS of G. A subset D of V which is a total dominating set, is a locating-total dominating set, or just a LTDS of G, if for any two distinct vertices u and v of V(G)∖D, N G ( u ) ∩ D ≠ N G ( v ) ∩ D . The locating-total domination number γ L t ( G ) is the minimum cardinality of a locating-total dominating set...

A Characterization of Multidimensional S -Automatic Sequences

Emilie Charlier, Tomi Kärki, Michel Rigo (2009)

Actes des rencontres du CIRM

An infinite word is S -automatic if, for all n ≥ 0 , its ( n + 1 ) st letter is the output of a deterministic automaton fed with the representation of n in the considered numeration system S . In this extended abstract, we consider an analogous definition in a multidimensional setting and present the connection to the shape-symmetric infinite words introduced by Arnaud Maes. More precisely, for d ≥ 2 , we state that a multidimensional infinite word x : ℕ d → Σ over a finite alphabet Σ is S -automatic for some abstract numeration...

A characterization of planar median graphs

Iztok Peterin (2006)

Discussiones Mathematicae Graph Theory

Median graphs have many interesting properties. One of them is-in connection with triangle free graphs-the recognition complexity. In general the complexity is not very fast, but if we restrict to the planar case the recognition complexity becomes linear. Despite this fact, there is no characterization of planar median graphs in the literature. Here an additional condition is introduced for the convex expansion procedure that characterizes planar median graphs.

Currently displaying 81 – 100 of 8549