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

Displaying 1021 – 1040 of 1226

Showing per page

An Oriented Version of the 1-2-3 Conjecture

Olivier Baudon, Julien Bensmail, Éric Sopena (2015)

Discussiones Mathematicae Graph Theory

The well-known 1-2-3 Conjecture addressed by Karoński, Luczak and Thomason asks whether the edges of every undirected graph G with no isolated edge can be assigned weights from {1, 2, 3} so that the sum of incident weights at each vertex yields a proper vertex-colouring of G. In this work, we consider a similar problem for oriented graphs. We show that the arcs of every oriented graph −G⃗ can be assigned weights from {1, 2, 3} so that every two adjacent vertices of −G⃗ receive distinct sums of outgoing...

An upper bound for domination number of 5-regular graphs

Hua Ming Xing, Liang Sun, Xue-Gang Chen (2006)

Czechoslovak Mathematical Journal

Let G = ( V , E ) be a simple graph. A subset S ⊆ V is a dominating set of G , if for any vertex u ∈ V - S , there exists a vertex v ∈ S such that u v ∈ E . The domination number, denoted by γ ( G ) , is the minimum cardinality of a dominating set. In this paper we will prove that if G is a 5-regular graph, then γ ( G ) ≤ 5 14 n .

An upper bound for maximum number of edges in a strongly multiplicative graph

Chandrashekar Adiga, Mahadev Smitha (2006)

Discussiones Mathematicae Graph Theory

In this note we give an upper bound for λ(n), the maximum number of edges in a strongly multiplicative graph of order n, which is sharper than the upper bounds given by Beineke and Hegde [3] and Adiga, Ramaswamy and Somashekara [2], for n ≥ 28.

An upper bound of a generalized upper Hamiltonian number of a graph

Martin Dzúrik (2021)

Archivum Mathematicum

In this article we study graphs with ordering of vertices, we define a generalization called a pseudoordering, and for a graph H we define the H -Hamiltonian number of a graph G . We will show that this concept is a generalization of both the Hamiltonian number and the traceable number. We will prove equivalent characteristics of an isomorphism of graphs G and H using H -Hamiltonian number of G . Furthermore, we will show that for a fixed number of vertices, each path has a maximal upper H -Hamiltonian...

An upper bound of the basis number of the strong product of graphs

Mohammed M.M. Jaradat (2005)

Discussiones Mathematicae Graph Theory

The basis number of a graph G is defined to be the least integer d such that there is a basis B of the cycle space of G such that each edge of G is contained in at most d members of B. In this paper we give an upper bound of the basis number of the strong product of a graph with a bipartite graph and we show that this upper bound is the best possible.

An upper bound on the basis number of the powers of the complete graphs

Salar Y. Alsardary (2001)

Czechoslovak Mathematical Journal

The basis number of a graph G is defined by Schmeichel to be the least integer h such that G has an h -fold basis for its cycle space. MacLane showed that a graph is planar if and only if its basis number is ≤ 2 . Schmeichel proved that the basis number of the complete graph K n is at most 3 . We generalize the result of Schmeichel by showing that the basis number of the d -th power of K n is at most 2 d + 1 .

An upper bound on the Laplacian spectral radius of the signed graphs

Hong-Hai Li, Jiong-Sheng Li (2008)

Discussiones Mathematicae Graph Theory

In this paper, we established a connection between the Laplacian eigenvalues of a signed graph and those of a mixed graph, gave a new upper bound for the largest Laplacian eigenvalue of a signed graph and characterized the extremal graph whose largest Laplacian eigenvalue achieved the upper bound. In addition, an example showed that the upper bound is the best in known upper bounds for some cases.

Analogues of cliques for oriented coloring

William F. Klostermeyer, Gary MacGillivray (2004)

Discussiones Mathematicae Graph Theory

We examine subgraphs of oriented graphs in the context of oriented coloring that are analogous to cliques in traditional vertex coloring. Bounds on the sizes of these subgraphs are given for planar, outerplanar, and series-parallel graphs. In particular, the main result of the paper is that a planar graph cannot contain an induced subgraph D with more than 36 vertices such that each pair of vertices in D are joined by a directed path of length at most two.

Currently displaying 1021 – 1040 of 1226